Approximability and Mathematical Relaxations

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 (see chapter 6), we construct such hard instance by using the reduction designed to prove the inapproximability