7
$\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).

Improve this question
$\endgroup$
7
  • 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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 2:14

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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, 2013 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, 2013 at 17:33
  • $\begingroup$ As a general observation regarding LP: what if the coefficients are real numbers? Is it a know algorithm which can assert the feasibility in polynomial time? I asked this or.stackexchange.com/questions/5858/… without an answer so far (at the time of this comment). $\endgroup$
    – C Marius
    Mar 5, 2021 at 16:36

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.