Beyond Worst-Case Analysis in Approximation Algorithms

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 guar-antees have been elusive. In this dissertation, we look beyond worst-case analysis to obtain improved ap-proximation 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 set-tings. 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 rando