Tutte Seminar - Jochen Könemann

On Generalizations of Network Design Problems with Degree Bounds

Abstract:

Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. Starting with Jain's elegant iterative rounding scheme for the generalized Steiner network problem, the technique has more recently lead to breakthrough results in the area of constrained network design, where a number of linear constraints are added to a classical network design problem. Most notable among recent successes is Singh & Lau's +1-algorithm [STOC, 2007] for the minimum-cost degree-bounded spanning tree problem. 

In this talk we further extend the scope of the iterative relaxation method in two ways: (1) by handling more complicated degree constraints in the minimum spanning tree problem, and (2) by incorporating `degree bounds' in other combinatorial optimization problems such as matroids, matroid intersection and lattice polyhedra.
Much of the talk will focus on (1). We consider the minimum crossing spanning tree (MCST) problem, where we are given an undirected, weighted graph, vertex sets S_1,...,S_k and degree bounds b_1,...,b_k. The goal is to find a mincost spanning tree in G that has at most b_i edges crossing S_i for all i. This problem generalizes the mincost degree-bounded spanning tree problem considered Singh & Lau. We consider the special case of the problem where the given vertex sets form a laminar family, and show that the additional structure of the cuts can be used to yield improved approximation algorithms.

This is joint work with N. Bansal, R. Khandekar, V. Nagarajan & B. Peis.