6
$\begingroup$

Given a linear system of the form:

$$\begin{array}{c} x_r = a \quad x_j = b \\ c_1x_1 + c_2x_2 + \ldots + c_nx_n = N \\ x_1+x_2 + x_3 + \ldots + x_n = k\\ 0 \le a,b,x_1,x_2,x_3...x_n \le 1\\ k \ge 0 \end{array}$$

How quickly can the feasibility of the system be checked? To clarify: $x_r,x_j$ are members of $x_1,x_2...x_n$. Would it be $O(n^{3.5})$ since I believe that is the general complexity for running a linear program or would it be less? Can one use gaussian elimination to quickly reduce the first 4 equations in $O(n^3)$ and after that systematically move through the equations starting from the terms with largest coefficient and moving to terms with smallest coefficient assigning values that bring the equations as close to satisfactory as possible?

Additional info:

I am assuming that the number of variables scales linearly. $n \ne N$ (I think that was clear though).

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Your proposed algorithm doesn't seem to work. Are you interested in a practical answer or in a theoretical answer? $\endgroup$ – Yuval Filmus Jul 21 '13 at 0:44
  • $\begingroup$ If the number of variables are constant, then the LP can be solved in linear time with respect to the number of constraints. I assume you can just take the dual of this LP to get constant number of variables, and solve it in $O(n)$ time. $\endgroup$ – Chao Xu Jul 21 '13 at 0:46
  • 1
    $\begingroup$ @Chao Xu: if you take the dual, don't you get a linear number of variables because of all the $x_i \leq 1$ inequalities? $\endgroup$ – Peter Shor Jul 21 '13 at 0:49
  • 1
    $\begingroup$ Why do you need to include $x_r$ and $x_j$ in the LP at all? Can't you get rid of these variables and replace the equalities with $\sum_{i \ne j,r} x_i = k' = k-x_r-x_j$ and $\sum_{i \ne j,r} c_i x_i = N' = N- c_r x_r - c_j x_j$? $\endgroup$ – Peter Shor Jul 21 '13 at 0:55
  • 1
    $\begingroup$ If I understand your question properly, they're both linear programs, and both solvable in polynomial time. If you're setting some of your variables to constants, why bother including them in the description of the LP? (Unless you'll be running this same LP many times with different variables set to constants, in which case you might be able to speed things up with some kind of preprocessing.) $\endgroup$ – Peter Shor Jul 21 '13 at 2:14
6
$\begingroup$

Restating the problem. As far as I can tell, your system is equivalent to the following:

$$c_1 x_1 + \dots + c_n x_n = N$$

subject to the constraints

$$0 \le x_1, \dots, x_n \le 1.$$

Solving this problem. This is a linear program, so certainly we can tell in polynomial time whether it has any feasible solution, as a result of the fact that there are polynomial-time algorithms for linear programming.

However, there's a better solution. We can directly solve this problem by inspection, without needing a linear programming solver.

Suppose without loss of generality that $c_1,\dots,c_j$ are positive and $c_{j+1},\dots,c_n$ are zero or negative. (You can re-order the variables to put things into this standard form.)

Then it follows that $c_1 x_1 + \dots + c_n x_n \le c_1 + \dots + c_j$. So, if $c_1 + \dots + c_j < N$, then this problem has no feasible solution. On the other hand, if $N \le c_1 + \dots + c_j$, then it is easy to demonstrate that this problem does have a solution: simply let $x_1 = \cdots = x_j = N/(c_1 + \dots + c_j)$ and let $x_{j+1} = \cdots = x_n = 0$. These $x_i$'s will all fall in the desired range.

Thus, feasibility can be checked in $O(n)$ time (in the RAM model, where basic operations take $O(1)$ time).

Details. Why is it fair game to reduce the problem to the form given above? How did I get the simpler form above?

Well, first off, I removed the variables $a,b$ from the linear program. No matter what values you assign to the $x$'s, you'll always be able to assign a value to $a,b$ derived from the $x$'s that satisfies the equations that mention $a,b$.

Similarly, I removed the equation $k=\dots$ and the variable, since no matter what value we assign to the other variables, we can simply set $k=x_1+\dots+x_n$ and get a value that will satisfy this equation; it will also satisfy $k\ge 0$, since all the $x_i$'s are required to be $\ge 0$. That leaves me with the problem shown at the top of my answer.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ You're assuming that $k$ is a variable. I thought $k$ was a positive constant that was given to you. The OP should clarify this. $\endgroup$ – Peter Shor Jul 21 '13 at 11:28
  • $\begingroup$ @PeterShor, good point. Thank you! I hope frogeyedpeas will clarify, if this assumption is not correct. My assumption that $k$ is a variable was based upon the inclusion of the constraint $k \ge 0$ in the OP's set of inequalities ... but you might be right, in which case my answer would be invalid. $\endgroup$ – D.W.♦ Jul 21 '13 at 17:33

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.