9
$\begingroup$

Per the title, other than using a general purpose LP solver, is there an approach for solving systems of inequalities over variables $x_i, \ldots, x_k$ where inequalities have the form $\sum_{i \in I} x_i < \sum_{j \in J} x_j$? What about the special case of inequalities that form a total order over the sums of the members of the power set of $\{x_i, \ldots, x_k\}$?

$\endgroup$
  • 4
    $\begingroup$ @Ankur: it doesn't matter whether it's integers or reals. If these are strict inequalities, you can round them off to rationals, and then multiply them by the least common denominator to get an integer solution. $\endgroup$ – Peter Shor May 6 '12 at 14:22
  • 6
    $\begingroup$ I have no idea what you can code in 30 minutes (in which language?). If that is the criterion for “simple,” is this really a question in theoretical computer science at all? $\endgroup$ – Tsuyoshi Ito May 6 '12 at 16:29
  • 1
    $\begingroup$ Good point Peter Shor. jonderry, I take my statement back. I was thinking that the combinatorial problem of satisfying these strict inequalities and the convex analytic problem of finding an interior point of a cone are qualitatively distinct. I was wrong. $\endgroup$ – Ankur May 6 '12 at 16:32
  • 1
    $\begingroup$ @Tsuyoshi: It doesn't need to be trivial, but I am curious to know if this can be done from first principles without using all of the extra power of a full LP solver, especially for the special case in which we have an ordering of all of the subset-sums (note in this case that polynomial time is exponential in the number of variables). $\endgroup$ – jonderry May 6 '12 at 16:41
  • 3
    $\begingroup$ Then I think that “Can this problem solved efficiently without using general algorithms for linear programming?” is a good way to formulate your question better. $\endgroup$ – Tsuyoshi Ito May 6 '12 at 19:20
9
$\begingroup$

For your first question, without the total order, the answer to your question is that it's essentially as hard as linear programming. Here's an outline of a proof.

First, let's establish a variable $x_1>0$, which we call $\epsilon$. Now, let's choose another variable $x_i$, which we will call $1$. We want to make sure that $$\epsilon \ll 1\, .$$ To do this, consider the inequalities $$x_1 < x_2,$$ $$x_1 + x_2 < x_3,$$ $$x_2+x_3 < x_4,$$ and so on. With a long enough chain, this will tell us that $Nx_1 < x_i$, or $\epsilon < 1/N$, for some very large $N$ ($N$ is a Fibonacci number, and so grows exponentially in $i$).

We can now manufacture a linear program with integer coefficients. If we want a coefficient of 3 on $x_t$, we add the inequalities $$x_t < x_{t'} < x_{t''} < x_t + \epsilon$$ and let $x_t + x_{t'} + x_{t''}$ stand in for 3$x_t$. If you want larger coefficients, you can get them by expressing the coefficients in binary notation, and making inequalities that guarantee that $x_u \approx 2x_t$, $x_v \approx 2x_u$, and so on. To get the right-hand-side, we do the same with the variable $x_i = 1$. This technique will let us use linear programs of the OP's form to approximately check feasibility for arbitrary linear programs with integer coefficients, a task which is essentially as hard as linear programming.

I don't know how to analyze the second question, asking about the case where there's a total order on all subsets.

$\endgroup$

Your Answer

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

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