On Generalizations of Network Design Problems with Degree Bounds
Speaker: | Jochen Könemann |
---|---|
Affiliation: | Norwich University |
Room: | Mathematics & Computer Building (MC) 5158 |
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.