Skip navigation
Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorArora, Sanjeeven_US
dc.contributor.authorManokaran, Rajsekaren_US
dc.contributor.otherComputer Science Departmenten_US
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.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=> library's main catalog </a>en_US
dc.subjectMathematical Relaxationen_US
dc.subject.classificationComputer scienceen_US
dc.subject.classificationApplied mathematicsen_US
dc.titleApproximability and Mathematical Relaxationsen_US
dc.typeAcademic dissertations (Ph.D.)en_US
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.