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.
|