Approximation via duality in offline, online and strategic settings

The main questions studied in this thesis can be broadly stated as follows: given an NP-hard combinatorial optimization problem and a suboptimal solution to this problem – obtained, for instance, by an efficient approximation algorithm – how close can this solution get to the optimal one? The quality of a solution is measured by the worst-case ratio, over all input instances, between the cost of the suboptimal solution and that of the optimal one. The aim of this thesis is to develop new techniques for proving tight bounds on this question for three fundamental classes of combinatorial optimization problems: covering, matching, and scheduling. Moreover, this question is studied in three different, yet related, contexts. These include the classical offline setting , where the entire input to a problem is known in advance; the online setting , where the input is revealed over time and algorithms must make irrevocable decisions; and a game-theoretic setting , where solutions arise as Nash equilibria. A unifying theme of this thesis is the use of convex programming relaxations, such as linear programming and semidefinite programming. These relaxations admit a rich duality theory, which is often exploited in order to construct carefully chosen dual solutions yielding tight performance guarantees.

• View at Worldcat

Full Text ( Final Version , 1mb )