Back to search

National and Kapodistrian University of Athens

Limitations of linear programming as a model of approximate computation

Abstract

dc:description

Linear programming has proved to be one of the most powerful and widely used tools inalgorithm design and especially in the design of approximation algorithms. It has provedits expressive power by modeling diverse types of problems in planning, routing, scheduling,assignment, and design. The popularity of linear programming raised the questionwhether for every algorithm there is a linear formulation or relaxation that captures itsmerits.In the last decade, the virtual "completeness" of linear programming-based algorithms wasquestioned. Although this line of thought goes at least as back as the late 80s with thefamous work of Yannakakis [66], it wasn’t until the early 00’s that the community startedto systematically study the limitations of linear programming methods. In particular,the first line of results that incarnated that questioning was the proof of the limitationsof lift-and-project methods for solving various problems. Those methods, when appliedto a relaxation, define hierarchies of increasingly strengthened relaxations. Their poweris such that proving a hardness result for some problem for a lift and project hierarchycan be taken as evidence that linear programming in general cannot efficiently solve thatproblem.Exploring the power of linear programming for combinatorial optimization problems hasbeen recently receiving renewed attention through the model of Extended Formulations.In this model we are concerned whether there are compact formulations or approximaterelaxations for combinatorial optimization problems, allowing the use of any set or typeof variables. The model of Extended Formulations is more general than that of lift-andprojecthierarchies and is arguably the most general model that truly captures pure linearprogramming methods.In this thesis we take the direction of exploring the limitation of linear programming.Most of the thesis’s results are concerned with linear programming approximability of thecapacitated versions of the metric facility location problem such as the capacitated facilitylocation (Cfl) and lower bounded facility location (Lbfl), problems which, while they canbe approximated within a constant factor using local search, they are not known to admit efficient relaxation based approximations. The failure for many years of the combinatorialoptimization community to devise efficient relaxations for such problems has created acertain sensation. We give impossibility results in the hierarchy and in the extendedformulations models and we also consider an other, independent family of relaxations.We note that our ideas and methods are of general value and independent interest. Thisis especially true for the extended formulations where we devise a general method forlower bounding the size of linear programs.Regarding our hierarchy related results, we show that the relaxations obtained from thenatural LP at Ω(n) levels of the semidefinite Lovasz-Schrijver hierarchy for mixed pro- ´grams, and at Ω(n) levels of the Sherali-Adams hierarchy, have an integrality gap of Ω(n),where n is the number of facilities of the instance. Both hierarchies yield an exact for-mulation for Cfl in at most n levels for the families of instances we consider and thusour bounds are asymptotically tight. For the families of instances we consider, bothhierarchies yield at the nth level an exact formulation for Cfl. Thus our bounds areasymptotically tight. Building on our methodology for the Sherali-Adams result, we provethat the standard Cfl relaxation enriched with the submodular inequalities of [1], a generalizationof the flow-cover valid inequalities, has also an Ω(n) gap and thus not boundedby any constant. This disproves a long-standing conjecture of [46].We propose a framework for proving lower bounds on the size of extended formulations.We do so by introducing specific types of extended relaxations that we call product anddistributional relaxations. Then we show that for every approximate extended formulationof a polytope P, there is a product or distributional relaxation that has the same size andis at least as strong. We provide a methodology for proving lower bounds on the sizeof approximate product and distributional relaxations by lower bounding the chromaticnumber of an underlying hypergraph, whose vertices correspond to gap-inducing vectors.As an application of our method we show for Cfl an exponential lower bound on the sizeof a restricted type of extended formulations which we call mixed product relaxations.We finally introduce the family of proper relaxations which generalizes to its logical extremethe classic star relaxation and captures general configuration-style LPs. We characterizethe behavior of proper relaxations for Cfl and Lbfl through a sharp threshold phenomenon.

Degree

thesis:*
Grantor dc:publisher
National and Kapodistrian University of Athens
Year dc:date
2015

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Moysoglou, Ioannis
  • Μωυσόγλου, Ιωάννης

Subjects

dc:subject × 14

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/44065

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Moysoglou, Ioannis; Μωυσόγλου, Ιωάννης. Limitations of linear programming as a model of approximate computation. National and Kapodistrian University of Athens, 2015. http://hdl.handle.net/10442/hedi/44065