# Lower bound on positive coefficients of the optimum of 0,1-linear programming problem

I have an instance linear programming such that the coefficients and the constant terms are 0 or 1. Formally, the set of variables is denoted as $$V$$ and $$|V| = n$$. There are $$m$$ constraints, formed as $$\mathbf{a}_{1}^{\top} \mathbf{v} \leq 1$$ or $$\mathbf{a}_{2}^{\top} \mathbf{v} \geq 1$$ where $$\mathbf{a}_{1}, \mathbf{a}_{2} \in \{0,1\}^{n}$$ and $$\mathbf{v} = [v_{1}, v_{2}, \ldots, v_{n}]^{\top}$$. (Assume that $$0 \leq v_{i} \leq 1$$).

The objective function is $$\min \sum_{i}v_{i} = [1,1, \ldots, 1] \cdot\mathbf{v}$$ I am hoping to find a constant $$c \geq 0$$ (depending only on $$n$$) such that there always exist an optimum $$\mathbf{v}^{*} \in [0,1]^{n}$$ satisfying $$v^{*}_{i} = 0$$ or $$v^{*}_{i} \geq c$$.

Does it hold for $$c = 1/n$$? Is there any positive lower bound on $$c$$?

For example, consider the LP relaxation of the vertex cover problem. The constraints are formed as $$v_{i} + v_{j} \geq 1$$, for each edge $$v_{i}v_{j} \in E(G)$$. We know that there exists a half-integral optimum, i.e., $$v_{i} \in \{0,1/2,1\}$$.

$$\frac 1n$$ is not a lower bound. For example, let $$n=10$$. Consider 3 set of equations (you can get equalities by considering both $$a^\top v \le 1$$ and $$a^\top v \ge 1$$):

1. \begin{align} v_1 + v_2 + v_3 \qquad = 1\\ \qquad v_2 + v_3 + v_4 = 1\\ v_1 \qquad + v_3 + v_4 = 1\\ v_1 + v_2 \qquad + v_4 = 1\\ \end{align} It's easy to check that $$v_1=v_2=v_3=v_4=\frac 13$$ is the unique solution.

2. Consider $$v_5 + v_6 + v_7 + v_8 + 0 \cdot v_9 = 1$$ and, similarly to the above case, all cyclic shifts of $$(v_5, \ldots, v_9)$$. Again, the unique solution is $$v_5 = v_6 = v_7 = v_8 = v_9 = \frac 14$$.

3. The last equation is $$v_1 + v_2 \qquad + v_5 \qquad + v_{10} = 1$$ Then $$v_{10} = 1 - 2 \cdot \frac 13 - \frac 14 = \frac 1 {12}$$.

Generalizing it, you can always obtain coefficient $$\frac 1{k (k+1)}$$ using $$2k + 4$$ variables.

I think that by properly selecting numbers $$p_1, \ldots, p_k$$, you should be able to get a coefficient as small as $$O\left(\frac 1 {\prod_i p_i}\right)$$ with $$O\left(\sum_i p_i\right)$$ variables.

• +1. By the way, do you know anything about 0,1-quadratic programming? This question of mine didn't get a lot of attention: cs.stackexchange.com/q/109039/61663, it's about a quadratic optimization problem on variables that can be in {-1,1}, which is equivalent to {0,1} if you just add 1 and divide by 2 on all variables. – Nike Dattani Apr 25 at 2:57
• @NikeDattani, sorry, don't know anything about it. About the question you've mentioned: I'm confused what kind of solution you want (I have the same confusion as Juho in comments). Do you want a poly-time approximation (in this case check ".878-Approximation Algorithms for MAX CUT") or do you want something that works reasonably well in practice (possibly without any guarantees)? – user114966 Apr 25 at 3:12
• It doesn't need to be poly-time. It just needs to work reasonably well in practice, and possibly without any guarantees. I can check out the .878-approximation algorithms, and if you were to suggest that in an answer, I wouldn't mind that either! – Nike Dattani Apr 25 at 4:52
• @NikeDattani, you may try approaches I mention here, except for spectral partitioning. They are for MIN-CUT, and it should be straightforward to adjust them for MAX-CUT. – user114966 Apr 26 at 1:00
• Thanks! That question was from 2 years ago and it will be a while before I can try these, would you consider writing a short answer on the question with some of these suggestions so that when I get around to doing the tests, I'll have the suggestions in one place? I may not remember to look at the comments of this question! – Nike Dattani Apr 26 at 1:06