PhD Defense: Primal-Dual Techniques for Online Algorithms and Mechanisms

Talk
Vahid Liaghat
Time: 
03.05.2015 10:00 to 12:00
Location: 

AVW 4172

An offline algorithm is one that knows the entire input in advance. An online algorithm, however, processes its input in a serial fashion. In contrast to offline algorithms, an online algorithm works in a local fashion and has to make irrevocable decisions without having the entire input. Online algorithms are often not optimal since their irrevocable decisions may turn out to be inefficient after receiving the rest of the input. For a given online problem, the goal is to design algorithms which are competitive against the offline optimal solutions.
In a classical offline scenario, it is often common to see a dual analysis of problems that can be formulated as a linear or convex program.
Primal-dual and dual-fitting techniques have been successfully applied to many such problems. Unfortunately, the usual tricks come short in an online setting since an online algorithm should make decisions without knowing even the whole program. In this thesis, we study the competitive analysis of fundamental problems in the literature such as different variants of online matching and online Steiner connectivity, via online dual techniques.
Although there are many generic tools for solving an optimization problem in the offline paradigm, much less is known for tackling online problems. A representative example is bipartite matching. Even though bipartite matching is easily computable in the offline setting, solving the problem online is shown to be very challenging. The main focus of this work is to design generic techniques for solving linear optimization problems where the solution space is restricted via a set of linear constraints. A general family of these problems are online packing/covering problems. Our work shows that for several seemingly unrelated problems, primal-dual techniques can be successfully applied as a unifying approach for analyzing these problems. We believe this leads to generic algorithmic frameworks for solving online problems.
In the first part of the thesis, we show the effectiveness of our techniques for both adversarial settings and stochastic settings in covering problems.
In particular, we introduce new techniques for solving two fundamental linear optimization problems, namely, the stochastic generalized assignment problem and the degree-bounded Steiner connectivity problem. The former, generalizes various problems such as online matching, ad allocation, bin packing, etc; while the latter establishes a starting point for the analysis of the important class of degree-bounded optimization on graphs, in the online setting. In the second part of the thesis, we focus on the covering problems. We develop the framework of Disk Painting for a general class of network design problems that can be characterized by proper functions. This class generalizes the node-weighted and edge-weighted variants of several well-known Steiner connectivity problems. We furthermore design a generic technique for solving the prize-collecting variants of these problems when there exists a dual analysis for the non-prize-collecting counterparts.
Hence, we solve the online prize-collecting variants of several network design problems for the first time.
Finally, we conclude by describing several challenges and open problems for venturing deeper into either of these major families of problems.
Examining Committee:
Committee Chair: - Dr. Mohammad Taghi Hajiaghayi
Dean's Representative: - Dr. Subramanian Raghavan
Committee Members: - Dr. Samir Khuller
- Dr. Aravind Srinivasan
- Dr. Hector Corrada Bravo