3
$\begingroup$

I'm wondering which is the approximation class of Minimum 0-1 Integer Programming if only non-negative integers are used. That is:

  • minimize $c^T \cdot x$,
  • with $x\in \{0,1\}^n$ and $c\in (\mathbb{Z}^*)^n$,
  • subject to $Ax \geq b$, where $A\in (\mathbb{Z}^*)^{m * n}$ and $b\in (\mathbb{Z}^*)^m$.

where $c^T$ is the transpose of vector $c$ and $\mathbb{Z}^*$ is the set of non-negative integers. Alternatively, $\mathbb{Z}^*$ could be replaced by the set of non-negative rationals, and we could force $b=(1,...,1)$ (it would be the same problem up to normalization).

If negative integers were allowed in $A$ and $b$, then this problem would be Minimum 0-1 Integer Programming, which is NPO-complete.

If $x$ were a vector of integers, rather than a vector of bits, then it would be Cover Integer Program (CIP), which can be approximated logarithmically according to "Improved approximations of packing and covering problems" by A. Srinivasan (1995).

There are many other known related problems with different variations, e.g. all elements in $A$ must be bits, $\geq$ is $\leq$ and min is max, there is a single inequation (i.e. $m = 1$), etc. I had some hope when I found this: https://www.nada.kth.se/~viggo/wwwcompendium/node199.html#7105, comments section, last sentence. However, $A$ is a matrix of bits in that work.

It is trivial to build an S-reduction from Minimum Set Cover, so at least it is Log-APX-hard. But at a first glance it looks too "simple" for Poly-APX- or Exp-APX-hardness, I don't know... Has this problem ever been studied?

EDIT: In the last two weeks I have developed an approximation to the problem (not based on linear programming) and, if my maths are right, it is logarithmic. Since it looks like this variant of Minimum 0-1 Integer Programming has not been studied yet in the literature, it could be publishable (?). I promise I'll get back here and report it, as soon as some reviewers check out its correctness (also if it's wrong, so that nobody else wastes his time trying the same!). (And, of course, if this problem has already been tackled in the literature, I would really appreciate it if you let me know!!)

EDIT2: As Chandra's answer says below, Kolloiopoulos and Young gave a logarithmic approximation to a generalization of this problem. They define $x$ as a vector of non-negative integers but, simultaneously, include constraints of the form $x \leq d$. By setting $d=(1,...,1)$, $x$ must be a vector of bits.

$\endgroup$
  • 1
    $\begingroup$ Srinivasan's algorithms work for this problem with the same guarantees because they use standard randomized rounding with the fractional part of an LP solution. $\endgroup$ – Sasho Nikolov Dec 30 '15 at 8:36
  • $\begingroup$ Thanks! I still have a doubt. You propose solving the LP relaxation and then rounding up or down the fractional LP solution, as usual. E.g. if we get x_1 = 0.2 in the LP solution then x_1 might become 0 in the ILP solution. Similarly, x_2 = 0.8 might become 1, x_3 = 1.3 may turn into 1, etc. But what do we do if x_4 = 6.8 and x_5 = 34.5 in the LP solution? Do they become x_4 = 1 and x_5 = 1?? If rounding is done like this then the LP solution would be a worthless approximation, right? Am I missing any trivlal "normalization" method to make 0 and 1 be the "true" natural rounding choices here? $\endgroup$ – EXPTIME-complete Dec 30 '15 at 16:42
  • $\begingroup$ (In particular, we cannot add "x_4 <= 1" to the list of constraints denoted by "Ax >= b" because those inequalities use >=, not <=.) $\endgroup$ – EXPTIME-complete Dec 30 '15 at 17:01
  • $\begingroup$ Wait a second... You cannot add "x_4 <= 1" to the problem I'm proposing above according to its definition, but you can add it to its LP relaxation counterpart indeed! Silly me! $\endgroup$ – EXPTIME-complete Dec 30 '15 at 17:15
  • 1
    $\begingroup$ That's right, but, actually, I take this back. The usual method of using randomized rounding for a covering problem involves scaling the solution up first by a log factor, and then randomly rounding the fractional part. The scaling can violate the 0-1 constraint. $\endgroup$ – Sasho Nikolov Dec 30 '15 at 17:23
4
$\begingroup$

Kolloiopoulos and Young give an $O(\log m)$ approximation for general covering integer programs. See the paper below. http://www.sciencedirect.com/science/article/pii/S0022000005000656

$\endgroup$
  • $\begingroup$ I had a (quick) look at Kolloiopoulos and Young's paper, and all I see is the case where $x\in (\mathbb{Z}^*)^n$. On the contrary, my question concerns the case where $x\in \{0,1\}^n$. Is there any trick that makes it work for the case $x\in \{0,1\}^n$ too? At a first glance, it looks like it is the same case as in the Srinivasan's paper I mentioned and commented with Sasho before, in the comments section above. $\endgroup$ – EXPTIME-complete Jan 21 '16 at 9:15
  • $\begingroup$ Take a closer look. $\endgroup$ – Chandra Chekuri Jan 21 '16 at 15:33
  • $\begingroup$ Yes, you are right. The "x \leq d" constraint, included in both problems addressed in the paper, lets us set d=(1, ..., 1). Since solutions must be non-negative integers, we get bits. Thank you very much! $\endgroup$ – EXPTIME-complete Jan 21 '16 at 21:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.