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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.