<p>Kolloiopoulos and Young give an $O(\log m)$ approximation for general covering integer programs. See the paper below.
<a href="http://www.sciencedirect.com/science/article/pii/S0022000005000656" rel="nofollow">http://www.sciencedirect.com/science/article/pii/S0022000005000656</a></p>

CC BY-SA 3.0
2016-01-21T09:15:01.343Z
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.
EXPTIME-complete
CC BY-SA 3.0
2016-01-21T15:33:38.160Z
Take a closer look.
Chandra Chekuri
CC BY-SA 3.0
2016-01-21T21:55:32.290Z
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!
EXPTIME-complete
CC BY-SA 3.0
2016-01-20T14:15:48.703Z
2016-01-20T14:15:48.703Z
Chandra Chekuri
<p>I'm wondering which is the approximation class of <em>Minimum 0-1 Integer Programming</em> if only non-negative integers are used. That is:</p>

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

<p>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).</p>

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

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

<p>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: <a href="https://www.nada.kth.se/~viggo/wwwcompendium/node199.html#7105" rel="nofollow">https://www.nada.kth.se/~viggo/wwwcompendium/node199.html#7105</a>, comments section, last sentence. However, $A$ is a matrix of bits in that work.</p>

<p>It is trivial to build an S-reduction from <em>Minimum Set Cover</em>, 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?</p>

<p>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  <em>Minimum 0-1 Integer Programming</em> 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!!)</p>

<p>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.</p>

CC BY-SA 3.0
2015-12-30T08:36:02.567Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-12-30T16:42:44.090Z
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?
EXPTIME-complete
CC BY-SA 3.0
2015-12-30T17:01:48.627Z
(In particular, we cannot add "x_4 <= 1" to the list of constraints denoted by "Ax >= b" because those inequalities use >=, not <=.)
EXPTIME-complete
CC BY-SA 3.0
2015-12-30T17:15:20.103Z
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!
EXPTIME-complete
CC BY-SA 3.0
2015-12-30T17:23:20.377Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-12-31T00:15:30.477Z
Ummm... So the 0-1 constraint could be violated. Thank you anyway, your idea made sense and was worth to be explored. It'd be weird if the problem I'm stating had not been studied before, it's quite a simple and "essential" variation of min 0-1 integer programming.
EXPTIME-complete
CC BY-SA 3.0
2015-12-31T00:28:30.553Z
(Btw, this problem is equivalent to some problem of computational marketing I'm facing, and I'd like to know whether it has already been studied, in particular before I decide investing many hours trying to develop an approximation by myself.)
EXPTIME-complete
CC BY-SA 3.0
2016-01-18T16:22:52.843Z
I have just edited my question to tell that I might have got an approximation to the problem (see the last paragraph).
EXPTIME-complete
CC BY-SA 3.0
2016-01-18T19:00:55.567Z
You could write to Aravind Srinivasan: he would know whether your problem is new or has been studied before, and what is known.
Sasho Nikolov
<complexity-classes><approximation-algorithms><integer-programming>
Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed?
EXPTIME-complete
# Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed?

(Asked by: username_0 on 2015-12-30)

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.

**Tags:** complexity-classes, approximation-algorithms, integer-programming
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  
> **username_0**: (In particular, we cannot add "x_4 <= 1" to the list of constraints denoted by "Ax >= b" because those inequalities use >=, not <=.)  
> **username_0**: 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!  
> **username_1**: 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.  
> **username_0**: Ummm... So the 0-1 constraint could be violated. Thank you anyway, your idea made sense and was worth to be explored. It'd be weird if the problem I'm stating had not been studied before, it's quite a simple and "essential" variation of min 0-1 integer programming.  
> **username_0**: (Btw, this problem is equivalent to some problem of computational marketing I'm facing, and I'd like to know whether it has already been studied, in particular before I decide investing many hours trying to develop an approximation by myself.)  
> **username_0**: I have just edited my question to tell that I might have got an approximation to the problem (see the last paragraph).  
> **username_1**: You could write to Aravind Srinivasan: he would know whether your problem is new or has been studied before, and what is known.  

---

## 1 answers

### Answer by username_2 on 2016-01-20. Score: 4 | Accepted answer

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>

> **Comments:**
> **username_0**: 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.  
> **username_2**: Take a closer look.  
> **username_0**: 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!  

---

