[Lowerbounds, Upperbounds]

Mohit Singh
Iterative Methods in Combinatorial Optimization
Friday, August 31, 2007
10:30 am
259 Posner

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. In this thesis proposal, we demonstrate that iterative methods give a general framework to analyze linear programming formulations of combinatorial optimization problems. We show that iterative methods are well-suited for problems in P and lead to new proofs of integrality of linear programming formulations for various problems in P. This understanding provides us the basic groundwork to address various problems that are NP-hard and to achieve good approximation algorithms.

In this thesis proposal, we focus on degree bounded network design problems. The most well-studied problem in this class is the Minimum Bounded Degree Spanning Tree problem. We present a polynomial time algorithm that returns a spanning tree of optimal cost and the degree
of any vertex in the tree exceeds its degree bound by at most an additive one. This generalizes a result of Furer and Raghavachari to weighted graphs, and thus settles a 15-year-old conjecture of Goemans affirmatively. This is essentially the best possible result for this problem. For degree constrained versions of more general network design problems, we obtain strong bi-criteria approximation algorithms.

We conclude the proposal with our plans for future work in this topic. We strongly believe that iterative methods will provide us with better understanding for solving related problems such as the Single Source Unsplittable Flow problem and the prize collecting variants of different combinatorial optimization problems. We further wish to study the similarities between the Total-Dual Integrality (TDI) method and the iterative methods proposed here.

47-853 Special Topics in Combinatorial Optimization: Iterative Relaxation and Rounding

Time: Mondays and Wednesdays 3.30-5.30 pm from August 27 - Oct 15 2007.

Place: Room 318, GSIA (old) building

Instructors: R. Ravi and Mohit Singh

Polyhedral methods have been a powerful tool in combinatorial optimization. In this course we will study exact linear programming formulations for a variety of problems which are polynomial time solvable. In particular, we will explore the effectiveness of a new technique based on iterative augmentation in proving some traditional results. We will also examine min-max relations and efficient algorithms for these problems. Towards the end of the class, we will illustrate the original iterative rounding method that inspired these results as well as some applications to approximation algorithms.

Tentative Outline:

1. Linear Programming
2. Bipartite and general matchings
3. Trees and connectivity augmentation
4. Matroid bases, intersection of two matroids
5. Union of matroids and packing trees
6. Submodular flow minimization
7. Graph orientations, Dilworth’s and Lucchesi-Younger theorems
8. Network design and degree constraints

Grades will be based on revising and correcting already prepared preliminary scribe notes, and on one or two problem sets over the course of the class. Solving any open problem posed in class will automatically absolve you from other work!
We require all attendees to register, if only for audit.

Monday, August 13, 3pm-4:30pm
Wean 7220

Title: Engineering Speed-Up Techniques for Shortest-Path Computations

Prof. Dr. Dorothea Wagner, Universität Karlsruhe, Germany
http://i11www.iti.uni-karlsruhe.de/members/wagner/

Abstract:

During the last years, impressive progress has been achieved in the field of algorithm engineering. One of the showpieces of algorithm engineering is the computation of shortest paths. In recent years, several speed-up techniques for Dijkstra’s shortest-path algorithm have been published that maintain the correctness of the algorithm but reduce its running time significantly for typical instances. They are usually based on a preprocessing that annotates the graph with additional information which can be used to prune or guide the search. Timetable information in public transport and route planning in road networks are traditional application domains for such techniques.

Results on the search space reduction are usually based on extensive experiments, in most cases with road data from US or Europe. However, one problem arising for algorithm engineering in general, and shortest paths in particular is that of data dependency of experimental results.

In this talk, we provide a condensed overview of new developments and extensions of classic results on speed-up techniques for shortest-path. In particular, we introduce a new methodology for evaluating the performance of speed-up techniques.