In a classical problem in scheduling, one has n unit size jobs with a precedence order and the goal is to find a schedule of those jobs on m identical machines as to minimize the makespan. It is one of the remaining f...
详细信息
ISBN:
(纸本)9781450341325
In a classical problem in scheduling, one has n unit size jobs with a precedence order and the goal is to find a schedule of those jobs on m identical machines as to minimize the makespan. It is one of the remaining four open problems from the book of Garey & Johnson whether or not this problem is NP-hard for m = 3. We prove that for any fixed epsilon and m, an LP-hierarchy lift of the time-index LP with a slightly super poly-logarithmic number of r = (log (n))(Theta(log log n)) rounds provides a (1 + epsilon)-approximation. For example Sherali-Adams suffices as hierarchy. This implies an algorithm that yields a (1 + epsilon)-approximation in time n(O(r)). The previously best approximation algorithms guarantee a 2 - 7/3m+1-approximation in polynomial time for m >= 4 and 4/3 for m = 3. Our algorithm is based on a recursive scheduling approach where in each step we reduce the correlation in form of long chains. Our method adds to the rather short list of examples where hierarchies are actually useful to obtain better approximation algorithms.
In the capacitated survivable network design problem (Cap-SNDP), we are given an undirected multi-graph where each edge has a capacity and a cost. The goal is to find a minimum cost subset of edges that satisfies a gi...
详细信息
In the capacitated survivable network design problem (Cap-SNDP), we are given an undirected multi-graph where each edge has a capacity and a cost. The goal is to find a minimum cost subset of edges that satisfies a given set of pairwise minimum-cut requirements. Unlike its classical special case of SNDP when all capacities are unit, the approximability of Cap-SNDP is not well understood;even in very restricted settings no known algorithm achieves a o(m) approximation, where m is the number of edges in the graph. In this paper, we obtain several new results and insights into the approximability of Cap-SNDP. We give an O(logn) approximation for a special case of Cap-SNDP where the global minimum cut is required to be at least R. (Note that this problem generalizes the min-cost lambda-edge-connected subgraph problem, which is the special case of our problem when all capacities are unit.) Our result is based on a rounding of a natural cut-based LP relaxation strengthened with knapsack-cover (KC) inequalities. Our technique extends to give a similar approximation for a new network design problem that captures global minimum cut as a special case. We then show that as we move away from global connectivity, even for the single pair case (that is, when only one pair (s,t) has positive connectivity requirement), this strengthened LP has Omega(n) integrality gap. We also consider a variant of Cap-SNDP in which multiple copies of an edge can be bought: we give an O(logk) approximation for this case, where k is the number of vertex pairs with non-zero connectivity requirement. This improves upon the previously known O(min{k,logR (max)})-approximation when R (max) is large;here R (max) is the largest requirement. On the other hand, we observe that the multiple copy version of Cap-SNDP is Omega(loglogn)-hard to approximate even for the single-source version of the problem.
We study the metric s-t path traveling salesman problem (TSP). An, Kleinberg, and Shmoys [Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 875-886] improved on the long-standing 5/3-approximatio...
详细信息
We study the metric s-t path traveling salesman problem (TSP). An, Kleinberg, and Shmoys [Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 875-886] improved on the long-standing 5/3-approximation factor and presented an algorithm that achieves an approximation factor of 1+root 5/2 approximate to 1.61803. Later, Sebo [Proceedings of the 16th Conference on Integer programming and Combinatorial Optimization, 2013, pp. 362-374] further improved the approximation factor to 8/5. We present a simple, self-contained analysis that unifies both results;our main contribution is a unified correction vector. Additionally, we compare two different linearprogramming (LP) relaxations of the s-t path TSP, namely, the path version of the Held-Karp LP relaxation for the TSP and a weaker LP relaxation, and we show that both LPs have the same (fractional) optimal value. Also, we show that the minimum cost of integral solutions of the two LPs are within a factor of 3/2 of each other. Furthermore, we prove that a half-integral solution of the stronger LP relaxation of cost c can be rounded to an integral solution of cost at most 3/2c. Finally, we give an example that presents obstructions to two natural methods that aim for an approximation factor of 3/2.
linearprogramming (LP) relaxations provide a powerfultechnique to design approximation algorithms for combinatorialoptimization problems. In the first part of the thesis, we studythe metric s-t path Traveling Salesma...
详细信息
linearprogramming (LP) relaxations provide a powerfultechnique to design approximation algorithms for combinatorialoptimization problems. In the first part of the thesis, we studythe metric s-t path Traveling Salesman Problem (TSP) via LPrelaxations. We first consider the s-t path graph-TSP, acritical special case of the metric s-t path TSP. We design a newsimple LP-based algorithm for the s-t path graph-TSP that achievesthe best known approximation factor of 1.5. Then, we turn ourattention to the general metric s-t path TSP. [An, Kleinberg, andShmoys, STOC 2012] improved on the long standing 5/3-approximationfactor and presented an algorithm that achieves an approximationfactor of (1+\sqrt{5})/2 \approx 1.61803. Later, [Sebo, IPCO 2013]further improved the approximation factor to 8/5. We present asimple, self-contained analysis that unifies both ***, we compare two different LP relaxations of the s-tpath TSP, namely the path version of the Held-Karp LP relaxationfor TSP and a weaker LP relaxation, and we show that both LPs havethe same (fractional) optimal value. Also, we show that the minimumcost of integral solutions of the two LPs are within a factor of3/2 of each other. Furthermore, we prove that a half-integralsolution of the stronger LP relaxation of cost c can be rounded toan integral solution of cost at most 3c/2. Finally, we give aninstance that presents obstructions to two natural methods that aimfor an approximation factor of 3/2. The Sherali-Adams (SA)system and the Lasserre (Las) system are two popularLift-and-Project systems that tighten a given LP relaxation in asystematic way. In the second part of the thesis, we study theAsymmetric Traveling Salesman Problem (ATSP) and unweighted TreeAugmentation Problem, respectively, in the framework of the SAsystem and the Las system. For ATSP, our focus is on negativeresults. For any fixed integer t>=0 and small \epsilon,00 can be any small constant, byanalyzing a combinatorial algorithm. T
A popular method in combinatorial optimization is to express polytopes P, which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of cons...
详细信息
ISBN:
(纸本)9781450327107
A popular method in combinatorial optimization is to express polytopes P, which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial. After two decades of standstill, recent years have brought amazing progress in showing lower bounds for the so called extension complexity, which for a polytope P denotes the smallest number of inequalities necessary to describe a higher dimensional polytope Q that can be linearly projected on P. However, the central question in this field remained wide open: can the perfect matching polytope be written as an LP with polynomially many constraints? We answer this question negatively. In fact, the extension complexity of the perfect matching polytope in a complete n -node graph is 22(111). By a known reduction this also improves the lower bound on the extension complexity for the TSP polytope from 2c1( '') to 22(111).
We consider a new combinatorial optimization problem that combines network design and facility location aspects. Given a graph with two types of customers and two technologies that can be installed on the edges, the o...
详细信息
We consider a new combinatorial optimization problem that combines network design and facility location aspects. Given a graph with two types of customers and two technologies that can be installed on the edges, the objective is to find a minimum cost subtree connecting all customers while the primary customers are served by a primary subtree that is embedded into the secondary subtree. In addition, besides fixed link installation costs, facility opening costs, associated to each node where primary and secondary subtree connect, have to be paid. The problem is called the Two Level Network Design Problem with Transition Facilities (TLNDF). We first model the problem on an extended graph where an additional set of arcs corresponds to the installation of node facilities and propose a cut set based model for the TLNDF that is defined on this extended graph. We present several theoretical results relating families of cut set inequalities on the extended graph with subfamilies of cut set inequalities on the original graph. We then show how a standard multi-commodity flow model defined on the original graph can be strengthened using disaggregation "by technology". We prove that the disaggregated compact formulation on the original graph provides the same lower bound as the cut set formulation on the extended graph. We develop a branch-and-cut algorithm for solving the TLNDF. The performance of this algorithm is improved by separating subfamilies of cut set inequalities on the original graph. Our computational study confirms the efficiency and applicability of the new approach. (C) 2012 Elsevier B.V. All rights reserved.
The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the...
详细信息
The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to 1.55 [Robins and Zelikovsky 2005]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP relaxation of Steiner tree with integrality gap smaller than 2 [Rajagopalan and Vazirani 1999]. In this article we present an LP-based approximation algorithm for Steiner tree with an improved approximation factor. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider an LP relaxation of the problem, which is based on the notion of directed components. We sample one component with probability proportional to the value of the associated variable in a fractional solution: the sampled component is contracted and the LP is updated consequently. We iterate this process until all terminals are connected. Our algorithm delivers a solution of cost at most ln(4) + epsilon < 1.39 times the cost of an optimal Steiner tree. The algorithm can be derandomized using the method of limited independence. As a by-product of our analysis, we show that the integrality gap of our LP is at most 1.55, hence answering the mentioned open question.
A well-studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fra...
详细信息
A well-studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxation for this problem into an integral solution that requires at most O(log n) additional bins. The three-permutations-problem of Beck is the following. Given any three permutations on n symbols, color the symbols red and blue, such that in any interval of any of those permutations, the number of red and blue symbols is roughly the same. The necessary difference is called the discrepancy. We establish a surprising connection between bin packing and Beck's problem: The additive integrality gap of the 3-partition linearprogramming relaxation can be bounded by the discrepancy of three permutations. This connection yields an alternative method to establish an O(log n) bound on the additive integrality gap of the 3-partition. Conversely, making use of a recent example of three permutations, for which a discrepancy of Omega(log n) is necessary, we prove the following: The O(log(2) n) upper bound on the additive gap for bin packing with arbitrary item sizes cannot be improved by any technique that is based on rounding up items. This lower bound holds for a large class of algorithms including the Karmarkar-Karp procedure.
Until recently, LP relaxations have only played a very limited role in the design of approximation algorithms for the Steiner tree problem. In particular, no (efficiently solvable) Steiner tree relaxation was known to...
详细信息
ISBN:
(纸本)9781450312455
Until recently, LP relaxations have only played a very limited role in the design of approximation algorithms for the Steiner tree problem. In particular, no (efficiently solvable) Steiner tree relaxation was known to have an integrality gap bounded away from 2, before Byrka et al. [3] showed an upper bound of approximate to 1.55 of a hypergraphic LP relaxation and presented a ln(4)+ epsilon approximate to 1.39 approximation based on this relaxation. Interestingly, even though their approach is LP based, they do not compare the solution produced against the LP value. We take a fresh look at hypergraphic LP relaxations for the Steiner tree problem one that heavily exploits methods and results from the theory of matroids and submodular functions which leads to stronger integrality gaps, faster algorithms, and a variety of structural insights of independent interest. More precisely, along the lines of the algorithm of Byrka et al. [3], we present a deterministic ln(4) approximation that compares against the LP value and therefore proves a matching ln(4) upper bound on the integrality gap of hypergraphic relaxations. Similarly to [3], we iteratively fix one component and update the LP solution. However, whereas in [3] the LP is solved at every iteration after contracting a component, we show how feasibility can be maintained by a greedy procedure on a well-chosen matroid. Apart from avoiding the expensive step of solving a hypergraphic LP at each iteration, our algorithm can be analyzed using a simple potential function. This potential function gives an easy means to determine stronger approximation guarantees and integrality gaps when considering restricted graph topologies. In particular, this readily leads to a 73/60 approximate to 1.217 upper bound on the integrality gap of hypergraphic relaxations for quasi-bipartite graphs. Additionally, for the case of quasi-bipartite graphs, we present a simple algorithm to transform an optimal solution to the bidirected cut rel
We consider the SURVIVABLE NETWORK DESIGN PROBLEM (SNDP) and the SYMMETRIC TRAVELING SALESMAN PROBLEM (STSP). We give simpler proofs of the existence of a 1/2-edge and 1-edge in any extreme point of the natural LP rel...
详细信息
We consider the SURVIVABLE NETWORK DESIGN PROBLEM (SNDP) and the SYMMETRIC TRAVELING SALESMAN PROBLEM (STSP). We give simpler proofs of the existence of a 1/2-edge and 1-edge in any extreme point of the natural LP relaxations for the SNDP and STSP, respectively. We formulate a common generalization of both problems and show our results by a new counting argument. We also obtain a simpler proof of the existence of a 1/2-edge in any extreme point of the set-pair LP relaxation for the element connectivity SURVIVABLE NETWORK DESIGN PROBLEM (SNDP(elt)). (C) 2010 Elsevier B.V. All rights reserved.
暂无评论