Approximability and Mathematical Relaxations

Abstract

The thesis ascertains the approximability of classic combinatorial

optimization problems using mathematical relaxations. The general

flavor of results in the thesis is: a problem P is hard to

approximate to a factor better than one obtained from the R

relaxation, unless the Unique Games Conjecture is false.

Almost optimal inapproximability is shown for a wide set of problems

including Metric Labeling, Max. Acyclic Subgraph, various packing

and covering problems. The key new idea in this thesis is in

coverting hard instances of relaxations (a.k.a integrality gap

instances) into a proof of inapproximability (assuming the UGC). In

most cases, the hard instances were discovered prior to this work;

our results imply that these hard instances are possibly strong

bottlenecks in designing approximation algorithms of better quality

for these problems.

For ordering problems such as Max Acyclic Subgraph and

Feedback Arc Set such hard instances were previously unknown.

For these problems, we construct such

hard instance by using the reduction designed to prove the

inapproximability. The hard instances show that all ordering

problems are hard to approximate to a factor larger than the

expected fraction satisfied by a random ordering: i.e., all ordering

CSPs are approximation resistant.

Techniques involve using mathematical relaxations to obtain local

distributions, converting them into low degree functions defined

over the boolean cube and using the invariance principle to analyse

such function.

I believe the thesis will be a good reference, both for the results

proven therein, and for the framework designed in ascertaining

approximability from mathematical relaxations.