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 (MAS), various packing
and covering problems. The key new idea in this thesis is in
converting 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 MAS 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 analyze
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.