Approximate fixed-rank closures of set covering problems

Daniel Bienstock (danocolumbia.edu)
Mark Zuckerberg (mz47columbia.edu)

Abstract: We show that for any fixed rank, the closure of a set covering problem (and related problems) can be approximated in polynomial time -- we can epsilon-approximate any linear program over the closure in polynomial time.

Keywords: integer programming

Category 1: Integer Programming (0-1 Programming )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Citation: CORC report TR-2003-01, Computational Optimization Research Center, Columbia University

Download: [PDF]

Entry Submitted: 08/26/2004
Entry Accepted: 08/26/2004
Entry Last Modified: 08/26/2004

Modify/Update this entry