Skip navigation
Please use this identifier to cite or link to this item:
Title: Approximability and Mathematical Relaxations
Authors: Manokaran, Rajsekar
Advisors: Arora, Sanjeev
Contributors: Computer Science Department
Keywords: Approximability
Mathematical Relaxation
Subjects: Computer science
Applied mathematics
Issue Date: 2012
Publisher: Princeton, NJ : Princeton University
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.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Computer Science

Files in This Item:
File Description SizeFormat 
Manokaran_princeton_0181D_10453.pdf624.06 kBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.