Approximating Generalized Covering Integer Programs
| Speaker: | Jochen Könemann |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
Many network design problems are naturally cast as 0,1 (set-) covering integer programs, where connectivity requirements are expressed through cut-covering constraints; e.g., a set of edges is feasible if each edge-cut is covered by a sufficient number of edges. In this talk we focus on capacitated covering problems, where the coverage supplied by a set for the elements it contains is an arbitrary non-negative number. Such problems are naturally modeled by so called column-restricted covering IPs (CCIPs).
For
a
given
CCIP,
we
define
two
related
0,1
covering
problems:
the
underlying
0,1
problems,
and
a
second,
priority
covering
problem.
Our
main
result
shows
that
the
given
CCIP
has
an
O(1)-approximation
if
the
natural
LP
formulations
for
two
induced
0,1
problems
have
O(1)
LP/IP
gap.
We
also
give
some
recent
applications
of
our
framework.
This
is
joint
work
with
Deeparnab
Chakrabarty,
and
Elyot
Grant.