[Lowerbounds, Upperbounds]

Iterative Methods in Combinatorial Optimization

Mohit Singh

Wednesday, April 30, 2008, 3:30 pm, 384 Posner

Abstract:

Linear programming has been a successful tool in combinatorial optimization to achieve polynomial time algorithms for problems in P and also to achieve good approximation algorithms for problems which are NP-hard. We demonstrate that iterative methods give a general framework to analyze linear programming formulations of polynomial time solvable problems as well as NP-hard problems.

In this thesis, we focus on degree bounded network design problems. The most well-studied problem in this class is the Minimum Bounded Degree Spanning Tree problem defined as follows. Given a weighted undirected graph with degree bound B, the task is to find a spanning tree of minimum cost that satisfies the degree bound. We present a polynomial time algorithm that returns a spanning tree of optimal cost and maximum degree B+1. This generalizes a result of Furer and Raghavachari to weighted graphs, and thus settles a 15-year-old conjecture of Goemans affirmatively. This is also the best possible result for the problem in polynomial time unless P=NP.

We also study degree bounded versions of general network design problems including the minimum bounded degree Steiner tree problem, the minimum bounded degree Steiner forest problem, minimum bounded degree k-edge connected subgraph problem and the minimum bounded degree arborescence problem. We show that iterative methods give bi-criteria approximation algorithms that return a solution whose cost is within a small constant factor of the optimal solution and the degree bounds are violated by an additive factor in undirected graphs and a small multiplicative factor in directed graphs. These results also imply first additive approximation algorithms for various degree constrained network design problems in undirected graphs.

We also show the generality of the iterative methods and apply it to the degree constrained matroid problem, multi-criteria spanning tree problem, multi-criteria matroid basis problem and the generalized assignment problem achieving or matching best known approximation algorithms for them.

Thesis Committee:
Prof. R. Ravi, Carnegie Mellon University (Chair)
Prof. Gerard Cornuejols, Carnegie Mellon University
Prof. Alan Frieze, Carnegie Mellon University
Prof. Michel Goemans, Massachusetts Institute of Technology
Prof. Anupam Gupta, Carnegie Mellon University

A while ago I checked out Beautiful Code from our library. Jon Bentley wrote chapter 3, which is about Quicksort, and paradoxically named the chapter “The Most Beautiful Code I Never Wrote”. This video is an extension of that chapter and will explain the name. I can recommend the talk, especially the third part in which he talks about the industrial implementation of qsort (that part starts shortly after 34:00).

April 30, 2008
Varun Gupta
12:00 PM, 1507 Newell-Simon Hall
Title: Optimal size-based scheduling with selfish users

Abstract:

We consider the online single-server job scheduling problem. It is known that to minimize the average response time of jobs in this setting, at all times the job with the shortest remaining service time must be scheduled. This requires that the server knows about the sizes of all the jobs. However, in the scenario where the server does not know the sizes of the jobs whereas the jobs know their own sizes, the server can not rely on the jobs to truthfully reveal their sizes since a job may reduce its own response time by misreporting. While there are mechanisms in the literature that achieve truthful revelation, such mechanisms are based on imposing a tax and hence involve “real” money - which is not always desirable.

In this work, we propose a novel token based scheduling game. We prove that while playing the above scheduling game, all the jobs trying to minimize their own response time will end up implementing the shortest remaining service time first scheduling policy themselves.