Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp013x816m65x
DC FieldValueLanguage
dc.contributor.authorManokaran, Rajsekaren_US
dc.contributor.otherComputer Science Departmenten_US
dc.date.accessioned2012-11-15T23:57:16Z-
dc.date.available2012-11-15T23:57:16Z-
dc.date.issued2012en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/dsp013x816m65x-
dc.description.abstractThe 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.en_US
dc.language.isoenen_US
dc.publisherPrinceton, NJ : Princeton Universityen_US
dc.relation.isformatofThe Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the <a href=http://catalog.princeton.edu> library's main catalog </a>en_US
dc.subjectApproximabilityen_US
dc.subjectInapproximabilityen_US
dc.subjectMathematical Relaxationen_US
dc.subject.classificationComputer scienceen_US
dc.subject.classificationApplied mathematicsen_US
dc.titleApproximability and Mathematical Relaxationsen_US