Modern computer science is very interested in finding efficient solutions to optimization problems. Many of these problems are NP-Hard and as a result, are unlikely to be solved optimally in a reasonable amount of time. In this context, we need new methods to devise meaningful solutions. Finding algorithms which guarantee an approximate solution to all instances has been a useful way to deal with this intractability. In this thesis, we consider two settings that have received wide interest in the theoretical computer science community: Online and Offline.

Approximation Algorithms (Offline Setting) Since the early 90's, there has been a great deal of success in providing approximate solutions to optimization problem when the entire input is present. In a wide variety of areas such as clustering, network design, vehicle routing and classical graph optimization, the quest for approximation algorithms developed new techniques. Approximation algorithms usually compute a good upper or lower bound (sometimes implicitly) and compare their output locally to these bounds. While this approach yields tight results for many problems, we pick problems in three areas where it falls short: Independent Sets in Sparse Graphs, Aversion K-clustering and Fractionally Sub-additive Network Design. For each of these problems, we achieve the best approximation ratios by using a new analysis which relies on understanding the global structure of the problem.

Online Algorithms Online algorithms have flourished as way to deal with decision making with incomplete information. While the worst-case analysis has been very useful, it often leads to very pessimistic bounds. To deal with this issue, we go beyond the worst-case setting and make conservative assumptions to relax the worst case setting. In this context, we study three classical problems: Online Matroid Intersection, Online Dynamic Bin Packing with recourse, and Smooth Online Convex Optimization. For each of the problem, we keep much of the worst-case competitive ratio model but make natural relaxations to achieve results that are not possible (or conjectured to be impossible) in the worst-case model.

Thesis Committee:
Aupam Gupta (Chair)
R. Ravi
Bernhard Haeupler
Nikhil Bansal (Eindhoven University of Technology)

Srinivasan Seshan, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

158 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]