Approximate fixed-rank closures of set covering problems

  • Daniel Bienstock
  • Mark Zuckerberg
    • Categories 0-1 Programming, Approximation Algorithms Tags Short URL: https://optimization-online.org/?p=9591

    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.

    Citation

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

    Article

    Download

    View PDF