Consider the following integer program (general covering):

$\min c \cdot x$ subject to

$Ax \ge b$,

where all entries in $A, b, c$ are nonnegative and $x$ is required to be nonnegative and integral.

In Vazirani, it is an exercise to show that an $O( \log n )$-approximation algorithm exists, where $A$ is an $n$ by $m$ matrix. Could someone give me a reference on how to do this?

In particular, I am interested in the case when $x$ is required to be binary, and in the use of linear programming to approximate.

  • 2
    $\begingroup$ If you really want the variables to be binary, it's a moderately challenging exercise. Here's a paper about it dl.acm.org/citation.cfm?id=1119632 that gives one method. It can be simplified a bit. $\endgroup$
    – Neal Young
    Apr 12 '13 at 5:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.