Friday, February 25, 2011
3:30 pm, MC 5158

Jochen Könemann
University of Waterloo

Approximating Generalized Covering Integer Programs

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.