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\}$.


1 Answer 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.

  • $\begingroup$ +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. $\endgroup$ Apr 25, 2021 at 2:57
  • $\begingroup$ @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)? $\endgroup$
    – user114966
    Apr 25, 2021 at 3:12
  • $\begingroup$ 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! $\endgroup$ Apr 25, 2021 at 4:52
  • $\begingroup$ @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. $\endgroup$
    – user114966
    Apr 26, 2021 at 1:00
  • $\begingroup$ 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! $\endgroup$ Apr 26, 2021 at 1:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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