Beyond Worst-Case Analysis in Approximation Algorithms

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+c} factor
approximation while running in time n^{ O(1/c) }, for every $c>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.