# linear programming with non-integer constraints

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?

• I just corrected the question, sorry for the wrong constraint: $x_v \ge 0$ – Xiao Apr 30 at 13:40
• 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 Apr 30 at 16:21
• Okay I'm deleting my comments on earlier versions of your post, as they no longer apply. – Neal Young Apr 30 at 22:48
• 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 May 9 at 14:39
• 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, 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 May 9 at 14:46