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
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).
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
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.
We consider the problem of packing a given number of congruent circles with the maximum radius in a unit square as a mathematical optimization problem. Due to the presence of non-overlapping constraints, this problem ...
详细信息
We consider the problem of packing a given number of congruent circles with the maximum radius in a unit square as a mathematical optimization problem. Due to the presence of non-overlapping constraints, this problem is a notoriously difficult nonconvex quadratically constrained optimization problem, which possesses many local optima. We consider several popular convexification techniques, giving rise to linear programming relaxations and semidefinite programmingrelaxations for the circle packing problem. We compare the strength of these relaxations theoretically, thereby proving the conjectures by Anstreicher. Our results serve as a theoretical justification for the ineffectiveness of existing machinery for convexification of non-overlapping constraints.
Yannakakis recently presented the first $\frac{3}{4}$-approximation algorithm for the Maximum Satisfiability Problem (MAX SAT). His algorithm makes nontrivial use of solutions to maximum flow problems. New, simple $\f...
详细信息
Yannakakis recently presented the first $\frac{3}{4}$-approximation algorithm for the Maximum Satisfiability Problem (MAX SAT). His algorithm makes nontrivial use of solutions to maximum flow problems. New, simple $\frac{3}{4}$-approximation algorithms that apply the probabilistic method/randomized rounding to the solution to a linearprogramming relaxation of MAX SAT are presented. It is shown that although standard randomized rounding does not give a good approximate result, the best solution of the two given by randomized rounding and a well-known algorithm of Johnson is always within $\frac{3}{4}$ of the optimal solution. It is further shown that an unusual twist on randomized rounding also yields 4-approximation algorithms. As a by-product of the analysis, a tight worst-case analysis of the relative duality gap of the linearprogramming relaxation is obtained.
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...
详细信息
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 and 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-indexed 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.
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.
暂无评论