<p>Suppose we have a linear progamming about vertex packing of a hypergraph (V,E), with size <span class="math-container">$n = \sum_{e \in E} |e|$</span>. We introduce a variable <span class="math-container">$x_v$</span> for each vertex <span class="math-container">$v \in V$</span>. The fractional version is stated as follows:</p>

<p><span class="math-container">$$\max \  \sum_{v \in V} x_v \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$</span>
<span class="math-container">$$s.t. \ \sum_{v: v \in e} x_v \le 1, \forall e \in E$$</span>
<span class="math-container">$$ x_v \ge 0, \forall v \in V$$</span></p>

<p>We have anonther version of this LP with non-integer constraints as follows:</p>

<p><span class="math-container">$$\max \sum_{v \in V} x_v \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$</span>
<span class="math-container">$$s.t. \ \sum_{v: v \in e} x_v \le 1, \forall e \in E$$</span>
<span class="math-container">$$x_v \in \{0, \log_N 2, \log_N 3, \cdots,  1\}, \forall v \in V$$</span></p>

<p>Let the optimal solution for these two LPs as <span class="math-container">$OPT_1$</span> and <span class="math-container">$OPT_2$</span>. </p>

<p>Is there any good upper bound for <span class="math-container">$N^{OPT_1}/N^{OPT_2}$</span> in terms of n and N?</p>

<p>Or: Assume <span class="math-container">$N = \Theta(n^n)$</span>. Is it possible to bound <span class="math-container">$N^{OPT_1}/N^{OPT_2} \le c$</span> for some constant c?</p>

CC BY-SA 4.0
2020-04-30T13:40:41.677Z
I just corrected the question, sorry for the wrong constraint: $x_v \ge 0$
Xiao
CC BY-SA 4.0
2020-04-30T16:21:50.263Z
Just rephase the whole question. The final target is to bound $N^{OPT_1}/N^{OPT_2}$ by a constant, under some assumption $N = \Theta(n^n)$. The $OPT_1 > OPT_2$ and $N^{OPT_1} > N^{OPT_2}$, so 1 is just the lower bound of their ratio, but not the upper bound.
Xiao
CC BY-SA 4.0
2020-04-30T22:48:14.977Z
Okay I'm deleting my comments on earlier versions of your post, as they no longer apply.
Neal Young
CC BY-SA 4.0
2020-05-09T14:39:26.030Z
For any instance that is symmetric (w.r.t. the vertices), the desired inequality holds as you can take the optimal (uniform) solution $x$ to $OPT_1$, then round each coordinate $x_v \ge 1/|V|$ down to its next allowed value for $OPT_2$.  By calculation this rounding will reduce the cost by $O(1/\log N)$.
Neal Young
CC BY-SA 4.0
2020-05-09T14:46:10.453Z
Maybe you can construct a counter-example by building a hypergraph out of $\Theta(n/k)$ independent copies of the hypergraph from the answer to [this post](https://cstheory.stackexchange.com/questions/46734/minimum-non-zero-variable-in-the-optimal-solution-of-linear-programming/46738#46738), each made with $k$ copies of the gadget?  The optimal fractional solution will have $\Theta(n/k)$ variables with value about $1/2^k$.  Take $k\approx \log n + \log\log n + O(1)$, so $1/2^k$ is about half the smallest allowed non-zero value for $OPT_2$.  Maybe $OPT_1 - OPT_2$ will be $\omega(1/\log N)$.
Neal Young
CC BY-SA 4.0
2020-05-09T21:43:40.967Z
On this counter-example, it seems thaat either rounding the minimum variable to 0 or $\log_N 2$ leads to a gap of $\omega(c^{n/\log n})$ for some constant c.
Xiao
CC BY-SA 4.0
2020-05-09T21:51:17.150Z
but i am not sure whether exists a better rounding strategy instead of just rounding to the nearest allowed values...
Xiao
<linear-programming>
linear programming with non-integer constraints
Xiao
# linear programming with non-integer constraints

(Asked by: username_0 on 2020-04-25)

Suppose we have a linear progamming about vertex packing of a hypergraph (V,E), with size $n = \sum\_{e \in E} |e|$. We introduce a variable $x\_v$ for each vertex $v \in V$. The fractional version is stated as follows:

$$\max \ \sum\_{v \in V} x\_v \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$
$$s.t. \ \sum\_{v: v \in e} x\_v \le 1, \forall e \in E$$
$$ x\_v \ge 0, \forall v \in V$$

We have anonther version of this LP with non-integer constraints as follows:

$$\max \sum\_{v \in V} x\_v \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$
$$s.t. \ \sum\_{v: v \in e} x\_v \le 1, \forall e \in E$$
$$x\_v \in \{0, \log\_N 2, \log\_N 3, \cdots, 1\}, \forall v \in V$$

Let the optimal solution for these two LPs as $OPT\_1$ and $OPT\_2$.

Is there any good upper bound for $N^{OPT\_1}/N^{OPT\_2}$ in terms of n and N?

Or: Assume $N = \Theta(n^n)$. Is it possible to bound $N^{OPT\_1}/N^{OPT\_2} \le c$ for some constant c?

**Tags:** linear-programming

> **Comments:**
> **username_0**: I just corrected the question, sorry for the wrong constraint: $x_v \ge 0$  
> **username_0**: Just rephase the whole question. The final target is to bound $N^{OPT_1}/N^{OPT_2}$ by a constant, under some assumption $N = \Theta(n^n)$. The $OPT_1 > OPT_2$ and $N^{OPT_1} > N^{OPT_2}$, so 1 is just the lower bound of their ratio, but not the upper bound.  
> **username_1**: Okay I'm deleting my comments on earlier versions of your post, as they no longer apply.  
> **username_1**: For any instance that is symmetric (w.r.t. the vertices), the desired inequality holds as you can take the optimal (uniform) solution $x$ to $OPT_1$, then round each coordinate $x_v \ge 1/|V|$ down to its next allowed value for $OPT_2$.  By calculation this rounding will reduce the cost by $O(1/\log N)$.  
> **username_1**: Maybe you can construct a counter-example by building a hypergraph out of $\Theta(n/k)$ independent copies of the hypergraph from the answer to [this post](https://cstheory.stackexchange.com/questions/46734/minimum-non-zero-variable-in-the-optimal-solution-of-linear-programming/46738#46738), each made with $k$ copies of the gadget?  The optimal fractional solution will have $\Theta(n/k)$ variables with value about $1/2^k$.  Take $k\approx \log n + \log\log n + O(1)$, so $1/2^k$ is about half the smallest allowed non-zero value for $OPT_2$.  Maybe $OPT_1 - OPT_2$ will be $\omega(1/\log N)$.  
> **username_0**: On this counter-example, it seems thaat either rounding the minimum variable to 0 or $\log_N 2$ leads to a gap of $\omega(c^{n/\log n})$ for some constant c.  
> **username_0**: but i am not sure whether exists a better rounding strategy instead of just rounding to the nearest allowed values...  

---

## 0 answers

