This paper presents approximation algorithms for two problems. First, a randomized algorithm guaranteeing approximation ratio rootn with high probability is proposed for the Max-Rep problem of [Kor98], or the Label-Co...
详细信息
ISBN:
(纸本)3540676902
This paper presents approximation algorithms for two problems. First, a randomized algorithm guaranteeing approximation ratio rootn with high probability is proposed for the Max-Rep problem of [Kor98], or the Label-Cover(MAX) problem (cf. [Hoc95]), where n is the number of vertices in the graph. This algorithm is then generalized into a 4 rootn-ratio algorithm for the nonuniform version of the problem. Secondly, it is shown that the Red-Blue Set Cover problem of [CDKM00] can be approximated with ratio 2 root nlog beta, where n is the number of sets and beta is the number of blue elements. Both algorithms can be adapted to the weighted variants of the respective problems, yielding the same approximation ratios.
We consider optimization problems that can be formulated as minimizing the cost of a feasible solution w(T)x over an arbitrary combinatorial feasible set F subset of {0,1}(n). For these problems we describe a broad cl...
详细信息
ISBN:
(纸本)9783642153686
We consider optimization problems that can be formulated as minimizing the cost of a feasible solution w(T)x over an arbitrary combinatorial feasible set F subset of {0,1}(n). For these problems we describe a broad class of corresponding stochastic problems where the cost vector W has independent random components, unknown at the time of solution. A natural and important objective that incorporates risk in this stochastic setting is to look for a feasible solution whose stochastic cost has a small tail or a small convex combination of mean and standard deviation. Our models can be equivalently reformulated as nonconvex programs for which no efficient algorithms are known. In this paper, we make progress on these hard problems. Our results are several efficient general-purpose approximation schemes. They use as a black-box (exact or approximate) the solution to the underlying deterministic problem and thus immediately apply to arbitrary combinatorial problems. For example, from an available delta-approximation algorithm to the linear problem, we construct a delta(1 + epsilon)-approximation algorithm for the stochastic problem, which invokes the linear algorithm only a logarithmic number of times in the problem input (and polynomial in 1/epsilon), for any desired accuracy level epsilon > 0. The algorithms are based on a geometric analysis of the curvature and approximability of the nonlinear level sets of the objective functions.
Motivated by applications in grid computing and project management;we study multiprocessor scheduling in scenarios where there is uncertainty in the successful execution of jobs when assigned to processors. We conside...
详细信息
ISBN:
(纸本)9781595936677
Motivated by applications in grid computing and project management;we study multiprocessor scheduling in scenarios where there is uncertainty in the successful execution of jobs when assigned to processors. We consider the problem of multiprocessor scheduling under uncertainty, in which we are given n unit-time jobs and m machines, a directed acyclic graph C giving the dependencies among the jobs, and for every job j and machine i, the probability p(ij) of the successful completion of job j when scheduled on machine i in any given particular step. The goal of the problem is to find a schedule that minimizes the expected makespan, that is, the expected completion time of all the jobs. The problem of multiprocessor scheduling under uncertainty was introduced by Malewicz and was shown to be NP-hard even when all the jobs are independent. In this paper, we present polynomial-time approximation algorithms for the problem;for special cases of the dag C. We obtain an O(log n)-approximation for the case of independent jobs, an O(log m log n log(n + m)/log log(n + m))-approximation when C is a collection of disjoint chains, an O(log m log(2) n)-approximation when C is a collection of directed out- or in-trees, and an O(log m log(2) n log(n + m)/log log(n + m))-approximation when C is a directed forest.
We consider the dynamic map labeling problem: given a set of rectangular labels on the map, the goal is to appropriately select visible ranges for all the labels such that no two consistent labels overlap at every sca...
详细信息
ISBN:
(纸本)9783319080161;9783319080154
We consider the dynamic map labeling problem: given a set of rectangular labels on the map, the goal is to appropriately select visible ranges for all the labels such that no two consistent labels overlap at every scale and the sum of total visible ranges is maximized. We propose approximation algorithms for several variants of this problem. For the simple ARO problem, we provide a 3c log n-approximation algorithm for the unit-width rectangular labels if there is a c-approximation algorithm for unit-width label placement problem in the plane;and a randomized polynomial-time O(log n log log n)-approximation algorithm for arbitrary rectangular labels. For the general ARO problem, we prove that it is NP-complete even for congruent square labels with equal selectable scale range. Moreover, we contribute 12-approximation algorithms for both arbitrary square labels and unit-width rectangular labels, and a 6-approximation algorithm for congruent square labels.
We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem. Given an asymmetric metric cost between n vertices, the problem is to find a Hamiltonian cycle that min...
详细信息
ISBN:
(纸本)9783642153686
We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem. Given an asymmetric metric cost between n vertices, the problem is to find a Hamiltonian cycle that minimizes its bottleneck (or maximum-length edge) cost. We achieve an O(logn/log log n) approximation performance guarantee by giving a novel algorithmic technique to shortcut Eulerian circuits while bounding the lengths of the shortcuts needed. This allows us to build on the recent result of Asadpour, Goemans, Madry, Oveis Gharan, and Saberi to obtain this guarantee. Furthermore, we show how our technique yields stronger approximation bounds in some cases, such as the bounded orientable genus case studied by Oveis Gharan and Saberi.
X-BalancedCC multiwinner voting rules constitute an attractive but computationally intractable compromise between the proportionality provided by the Monroe rule and the diversity provided by the Chamberlin-Courant ru...
详细信息
ISBN:
(纸本)9781450363099
X-BalancedCC multiwinner voting rules constitute an attractive but computationally intractable compromise between the proportionality provided by the Monroe rule and the diversity provided by the Chamberlin-Courant rule. We show how to use the Greedy-Monroe algorithm to get improved approximation results for the X-BalancedCC rules and for the Chamberlin-Courant rule, by appropriately setting a " schedule" for the sizes of virtual districts. We describe a polynomial-time algorithm for computing a schedule that guarantees high approximation ratio, but show that finding the best possible schedule for a given election is NP-hard. We further evaluate our algorithms experimentally and show that they perform very well in practice.
Motivated by issues in allocating limited preventative resources to protect a landscape against the spread of a wildfire from a stochastic ignition point, we give approximation algorithms for a new family of stochasti...
详细信息
ISBN:
(纸本)9783642291159
Motivated by issues in allocating limited preventative resources to protect a landscape against the spread of a wildfire from a stochastic ignition point, we give approximation algorithms for a new family of stochastic optimization problems. We study several models in which we are given a graph with edge costs and node values, a budget, and a probabilistic distribution over ignition nodes: the goal is to find a budget-limited set of edges whose removal protects the largest expected value from being reachable from a stochastic ignition node. In particular, 2-stage stochastic models capture the tradeoffs between preventative treatment and real-time response. The resulting stochastic cut problems are interesting in their own right, and capture a number of related interdiction problems, both in the domain of computational sustainability, and beyond. In trees, even the deterministic problem is (weakly) NP hard: we give a Polynomial-time approximation scheme for the single-stage stochastic case in trees when the number of scenarios is constant. For the 2-stage stochastic model in trees we give a -approximation in trees which violates the budget by a factor of at most 2 (delta is the tree diameter), and a 0.387-approximation that is budget-balanced. For the single-stage stochastic case in trees we can save (1- (1 - 1/delta) (delta)) OPT without violating the budget. Single-stage results extend to general graphs with an additional O(log n) loss in budget-balancedness. Multistage results have a similar extension when the number of scenarios is constant. In an extension of the single-stage model where both ignition and spread are stochastic we give a -approximation in trees. Our approximation guarantees in trees also hold for multistage and probabilistic-element-failure generalizations of the Maximum Coverage with Knapsack Constraint problem (MCKP).
Numerous approaches study the vulnerability of networks against social contagion. Graph burning studies how fast a contagion, modeled as a set of fires, spreads in a graph. The burning process takes place in synchrono...
详细信息
ISBN:
(数字)9783030148126
ISBN:
(纸本)9783030148119;9783030148126
Numerous approaches study the vulnerability of networks against social contagion. Graph burning studies how fast a contagion, modeled as a set of fires, spreads in a graph. The burning process takes place in synchronous, discrete rounds. In each round, a fire breaks out at a vertex, and the fire spreads to all vertices that are adjacent to a burning vertex. The selection of vertices where fires start defines a schedule that indicates the number of rounds required to burn all vertices. Given a graph, the objective of an algorithm is to find a schedule that minimizes the number of rounds to burn graph. Finding the optimal schedule is known to be NP-hard, and the problem remains NP-hard when the graph is a tree or a set of disjoint paths. The only known algorithm is an approximation algorithm for disjoint paths, which has an approximation ratio of 1.5. We present approximation algorithms for graph burning. For general graphs, we introduce an algorithm with an approximation ratio of 3. When the graph is a tree, we present another algorithm with approximation ratio 2. Moreover, we consider a setting where the graph is a forest of disjoint paths. In this setting, when the number of paths is constant, we provide an optimal algorithm which runs in polynomial time. When the number of paths is more than a constant, we provide two approximation schemes: first, under a regularity condition where paths have asymptotically equal lengths, we show the problem admits an approximation scheme which is fully polynomial. Second, for a general setting where the regularity condition does not necessarily hold, we provide another approximation scheme which runs in time polynomial in the size of the graph.
We are motivated by the developments in all-optical networks - a new technology that supports high bandwidth demands. These networks provide a set of lightpaths which can be seen as high-bandwidth pipes on which commu...
详细信息
ISBN:
(纸本)3540411437
We are motivated by the developments in all-optical networks - a new technology that supports high bandwidth demands. These networks provide a set of lightpaths which can be seen as high-bandwidth pipes on which communication is performed. Since the capacity enabled by this technology substantially exceeds the one provided by conventional networks, its ability to recover from failures within the optical layer is important. In this paper we study the design of a survivable optical layer. We assume that an initial set of lightpaths (designed according to the expected communication pattern) is given, and we are targeted at augmenting this initial set with additional lightpaths such that the result will guarantee survivability. For this purpose, we define and motivate a ring partition survivability condition that the solution must satisfy. Generally speaking, this condition states that lightpaths must be arranged in rings. The cost of the solution found is the number of lightpaths in it. This cost function reflects the switching cost of the entire network. We present some negative results regarding the tractability and approximability of this problem, and an approximation algorithm for it. We analyze the performance of the algorithm for the general case (arbitrary topology) as well as for some special cases.
This paper addresses the problem of traffic grooming in WDM rings in which all traffic emanates from a single node and all other nodes are destination nodes. This "one-to-many" scenario arises in metropolita...
详细信息
ISBN:
(纸本)9781424434343
This paper addresses the problem of traffic grooming in WDM rings in which all traffic emanates from a single node and all other nodes are destination nodes. This "one-to-many" scenario arises in metropolitan access networks in which one node serves as a "hub" connecting the ring to a larger network as well as in video-on-demand and other multimedia services where a single source node serves a collection of subscriber nodes. The ring comprises a given number of wavelengths of uniform capacity and a variable number of tunable Add-Drop Multiplexers (ADMs) at each node. Given a set of requests at the destination nodes, where each request comprises a bandwidth demand and a profit for fulfilling the request, our objective is to select a subset of the requests and pack ("groom") them onto the wavelengths such that no wavelength's capacity is exceeded and the total profit of the selected requests is maximized. Although this problem is NP-complete, we give polynomial time approximation algorithms with excellent theoretical performance validated with experimental results.
暂无评论