Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Local Constraints in Combinatorial Optimization

Madhur Tulsiani

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2009-175
December 16, 2009

http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-175.pdf

Hard combinatorial optimization problems are often approximated using linear or semidefinite programming relaxations. In fact, most of the algorithms developed using such convex programs have special structure: the constraints imposed by these algorithms are local i.e. each constraint involves only few variables in the problem. In this thesis, we study the power of such local constraints in providing an approximation for various optimization problems. We study various models of computation defined in terms of such programs with local constraints. The resource in question for these models is are the sizes of the constraints involved in the program. Known algorithmic results relate this notion of resources to the time taken for computation in a natural way. Such models are provided by the ``hierarchies" of linear and semidefinite programs, like the ones defined by Lov'{a}sz and Schrijver; Sherali and Adams; and Lasserre}. We study the complexity of approximating various optimization problems using each of these hierarchies. This thesis contains various lower bounds in this computational model. We develop techniques for reasoning about each of these hierarchies and exhibiting various combinatorial objects whose local properties are very different from their global properties. Such lower bounds {em unconditionally} rule out a large class of algorithms (which captures most known ones) for approximating the problems such as Max 3-SAT, Minimum Vertex Cover, Chromatic Number and others studied in this thesis. We also provide a positive result where a simple semidefinite relaxation is useful for approximating a constraint satisfaction problem defined on graphs, if the underlying graph is expanding. We show how expansion connects the local properties of the graph to the global properties of interest, thus providing a good algorithm.

Advisor: Luca Trevisan


BibTeX citation:

@phdthesis{Tulsiani:EECS-2009-175,
    Author = {Tulsiani, Madhur},
    Title = {Local Constraints in Combinatorial Optimization},
    School = {EECS Department, University of California, Berkeley},
    Year = {2009},
    Month = {Dec},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-175.html},
    Number = {UCB/EECS-2009-175},
    Abstract = {Hard combinatorial optimization problems are often approximated using linear or semidefinite programming relaxations. In fact, most of the algorithms developed using such convex programs have special structure: the constraints imposed by these algorithms are local i.e. each constraint involves only few variables in the problem. In this thesis, we study the power of such local constraints in providing an approximation for various optimization problems.

We study various models of computation defined in terms of such programs with local constraints. The resource in question for these models is are the sizes of the constraints involved in the program. Known algorithmic results relate this notion of resources to the time taken for computation in a natural way.

Such models are provided by the ``hierarchies"  of linear and semidefinite
programs, like the ones defined by Lov'{a}sz and Schrijver; Sherali and Adams; and Lasserre}. We study the complexity of approximating various optimization problems using each of these hierarchies.

This thesis contains various lower bounds in this computational model. We develop techniques for reasoning about each of these hierarchies and exhibiting various combinatorial objects whose local properties are very different from their global properties. Such lower bounds {em unconditionally} rule out a large class of algorithms (which captures most known ones) for approximating the problems such as Max 3-SAT, Minimum Vertex Cover, Chromatic Number and others studied in this thesis.

We also provide a positive result where a simple semidefinite relaxation is useful for approximating a constraint satisfaction problem defined on graphs, if the underlying graph is expanding. We show how expansion connects the local properties of the graph to the global properties of interest,
thus providing a good algorithm.}
}

EndNote citation:

%0 Thesis
%A Tulsiani, Madhur
%T Local Constraints in Combinatorial Optimization
%I EECS Department, University of California, Berkeley
%D 2009
%8 December 16
%@ UCB/EECS-2009-175
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-175.html
%F Tulsiani:EECS-2009-175