Skip navigation
Please use this identifier to cite or link to this item:
Title: Beyond Worst Case Analysis in Approximation Algorithms
Authors: Vijayaraghavan, Aravindan
Advisors: Charikar, Moses
Contributors: Computer Science Department
Keywords: Approximation Algorithms
Average Case Analysis
Balanced Cut
Dense subgraph
Graph Partitioning
semi-random models
Subjects: Computer science
Issue Date: 2012
Publisher: Princeton, NJ : Princeton University
Abstract: Worst-case analysis has had many successes over the last few decades, and has been the tool of choice in analyzing approximation guarantees of algorithms. Yet, for several important optimization problems, approximation algorithms with good guarantees have been elusive. In this dissertation, we look beyond worst-case analysis to obtain improved approximation guarantees for fundamental graph optimization problems, given that real-world instances are unlikely to behave like worst-case instances. We study average-case models and other structural assumptions that seem to capture properties of real-world instances, and design improved approximation algorithms in these settings. In some cases, this average-case study also gives us surprising insights into the worst-case approximability. In the first part of the thesis, we design better algorithms for realistic average-case instances of graph partitioning. We propose and study a semi-random model for graph partitioning problems, that is more general than previously studied random models, and that we believe captures many real-world instances well. We design new constant factor approximation algorithms for classical graph partitioning problems like Balanced Separator, Multicut, Small set expansion and Sparsest cut for these semi-random instances. We also explore how other assumptions about the stability of a planted solution can lead to improved approximation guarantees. In the second part of the thesis, we consider the Densest k-Subgraph problem, which is an important, yet poorly understood problem, from both average-case and worst-case perspectives. We first study a natural average-case version of the problem and design new counting-based algorithms with improved guarantees. These average-case algorithms directly inspire new worst-case algorithms, which surprisingly match our guarantees from the average-case: our algorithms use linear-programming hierarchies to give a n^{1/4+\epsilon} factor approximation while running in time n^{O(1/\epsilon)}, for every \epsilon> 0. This natural average-case model also identifies a concrete barrier for progress on Densest k-subgraph, and seems to captures exactly the extent of current approaches. These results suggest that the approximability of the Densest k-subgraph problem may be similar from both worst-case and average-case perspectives, in contrast to graph partitioning.
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 
Vijayaraghavan_princeton_0181D_10384.pdf855.91 kBAdobe PDFView/Download

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