Local Constraints in Combinatorial Optimization
- Author(s): Tulsiani, Madhur
- Advisor(s): Trevisan, Luca
- et al.
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