Spelling suggestions: "subject:"1inear programming relaxations"" "subject:"alinear programming relaxations""
1 |
Algorithmic aspects of connectivity, allocation and design problemsChakrabarty, Deeparnab 23 May 2008 (has links)
Most combinatorial optimization problems are
NP -hard, which imply that under well- believed complexity assumptions, there exist no polynomial time
algorithms to solve them. To cope with the NP-hardness, approximation algorithms which return solutions close to
the optimal, have become a rich field of study. One successful method for designing approx-
imation algorithms has been to model the optimization problem as an integer program and
then using its polynomial time solvable linear programming relaxation for the design and
analysis of such algorithms. Such a technique is called the LP-based technique.
In this thesis, we study the algorithmic aspects of three classes of combinatorial optimization problems
using LP-based techniques as our main tool.
Connectivity Problems:
We study the Steiner tree problem and devise new linear pro-
gramming relaxations for the problem. We show an equivalence of our relaxation with the
well studied bidirected cut relaxation for the Steiner tree problem. Furthermore, for a class
of graphs called quasi-bipartite graphs, we improve the best known upper bound on the
integrality gap from 3/2 to 4/3. Algorithmically, we obtain fast and simple approximation
algorithms for the Steiner tree problem on quasi-bipartite graphs.
Allocation Problems:
We study the budgeted al location problem of allocating a set of
indivisible items to a set of agents who bid on it but possess a hard budget constraint more
than which they are unwilling to pay. This problem is a special case of submodular welfare
maximization. We use a natural LP relaxation for the problem and improve the best known
approximation factor for the problem from ~ 0.632 to 3/4. We also improve the inapprox-
imability factor of the problem to 15/16 and use our techniques to show inapproximability
results for many other allocation problems.
We also study online allocation problems where the set of items are unknown and appear one at a time.
Under some necessary assumptions we provide online algorithms for
many problems which attain the (almost) optimal competitive ratio. Both these works have
applications in the area of budgeted auctions, the most famous of which are the sponsored
search auctions hosted by search engines on the Internet.
Design Problems:
We formally define and study design problems which asks how the
weights of an input instance can be designed, so that the minimum (or maximum) of
a certain function of the input can be maximized (respectively, minimized). We show
if the function can be approximated to any factor $alpha$, then the optimum design can be
approximated to the same factor.
We also show that (max-min) design problems are dual to packing problems. We use
the framework developed by our study of design problems to obtain results about fraction-
ally packing Steiner trees in a "black-box" fashion. Finally, we study integral packing of
spanning trees and provide an alternate proof of a theorem of Nash-Williams and Tutte
about packing spanning trees.
|
2 |
Integrality Gaps for Strong Linear Programming and Semidefinite Programming RelaxationsGeorgiou, Konstantinos 17 February 2011 (has links)
The inapproximability for NP-hard combinatorial optimization problems lies in the heart of theoretical computer science. A negative result can be either conditional, where the starting point is a complexity assumption, or unconditional, where the inapproximability holds for a restricted model of computation.
Algorithms based on Linear Programming (LP) and Semidefinite Programming (SDP) relaxations are among the most prominent models of computation. The related and common measure of efficiency is the integrality gap, which sets the limitations of the associated algorithmic schemes. A number of systematic procedures, known as lift-and-project systems, have been proposed to improve the integrality gap of standard relaxations. These systems build strong hierarchies of either LP relaxations, such as the Lovasz-Schrijver (LS) and the Sherali-Adams (SA) systems, or SDP relaxations, such as the Lovasz-Schrijver SDP (LS+), the Sherali-Adams SDP (SA+) and the Lasserre (La) systems.
In this thesis we prove integrality gap lower bounds for the aforementioned lift-and-project systems and for a number of combinatorial optimization problems, whose inapproximability is yet unresolved. Given that lift-and-project systems produce relaxations that have given the best algorithms known for a series of combinatorial problems, the lower bounds can be read as strong evidence of the inapproximability of the corresponding optimization problems. From the results found in the thesis we highlight the following:
For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) LS+ relaxation of the Vertex Cover polytope has integrality gap 2-epsilon.
The integrality gap of the standard SDP for Vertex Cover remains 2-o(1) even if all hypermetric inequalities are added to the relaxation. The resulting relaxations are incomparable to the SDP relaxations derived by the LS+ system. Finally, the addition of all ell1 inequalities eliminates all solutions not in the integral hull.
For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) SA relaxation of Vertex Cover has integrality gap 2-epsilon. The integrality gap remains tight even for superconstant-level SA+ relaxations.
We prove a tight lower bound for the number of tightenings that the SA system needs in order to prove the Pigeonhole Principle. We also prove sublinear and linear rank bounds for the La and SA systems respectively for the Tseitin tautology.
Linear levels of the SA+ system treat highly unsatisfiable instances of fixed predicate-P constraint satisfaction problems over q-ary alphabets as fully satisfiable, when the satisfying assignments of the predicates P can be equipped with a balanced and pairwise independent distribution.
We study the performance of the Lasserre system on the cut polytope. When the input is the complete graph on 2d+1 vertices, we show that the integrality gap is at least 1+1/(4d(d+1)) for the level-d SDP relaxation.
|
3 |
Integrality Gaps for Strong Linear Programming and Semidefinite Programming RelaxationsGeorgiou, Konstantinos 17 February 2011 (has links)
The inapproximability for NP-hard combinatorial optimization problems lies in the heart of theoretical computer science. A negative result can be either conditional, where the starting point is a complexity assumption, or unconditional, where the inapproximability holds for a restricted model of computation.
Algorithms based on Linear Programming (LP) and Semidefinite Programming (SDP) relaxations are among the most prominent models of computation. The related and common measure of efficiency is the integrality gap, which sets the limitations of the associated algorithmic schemes. A number of systematic procedures, known as lift-and-project systems, have been proposed to improve the integrality gap of standard relaxations. These systems build strong hierarchies of either LP relaxations, such as the Lovasz-Schrijver (LS) and the Sherali-Adams (SA) systems, or SDP relaxations, such as the Lovasz-Schrijver SDP (LS+), the Sherali-Adams SDP (SA+) and the Lasserre (La) systems.
In this thesis we prove integrality gap lower bounds for the aforementioned lift-and-project systems and for a number of combinatorial optimization problems, whose inapproximability is yet unresolved. Given that lift-and-project systems produce relaxations that have given the best algorithms known for a series of combinatorial problems, the lower bounds can be read as strong evidence of the inapproximability of the corresponding optimization problems. From the results found in the thesis we highlight the following:
For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) LS+ relaxation of the Vertex Cover polytope has integrality gap 2-epsilon.
The integrality gap of the standard SDP for Vertex Cover remains 2-o(1) even if all hypermetric inequalities are added to the relaxation. The resulting relaxations are incomparable to the SDP relaxations derived by the LS+ system. Finally, the addition of all ell1 inequalities eliminates all solutions not in the integral hull.
For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) SA relaxation of Vertex Cover has integrality gap 2-epsilon. The integrality gap remains tight even for superconstant-level SA+ relaxations.
We prove a tight lower bound for the number of tightenings that the SA system needs in order to prove the Pigeonhole Principle. We also prove sublinear and linear rank bounds for the La and SA systems respectively for the Tseitin tautology.
Linear levels of the SA+ system treat highly unsatisfiable instances of fixed predicate-P constraint satisfaction problems over q-ary alphabets as fully satisfiable, when the satisfying assignments of the predicates P can be equipped with a balanced and pairwise independent distribution.
We study the performance of the Lasserre system on the cut polytope. When the input is the complete graph on 2d+1 vertices, we show that the integrality gap is at least 1+1/(4d(d+1)) for the level-d SDP relaxation.
|
Page generated in 0.1082 seconds