2
$\begingroup$

I've come across a programming question. I can't solve it but I can write the question in mathematical form as follow:

Receive k equations,and for each equation receive 3 variables a, b, and c in the following form:

ax + by + cz >= 0

This is an example input of k = 4:

1) 2x + 1y + 0z >= 0

2) 1x - 2y + 0z >= 0

3) 3x + 3y - 50z >= 0

4) -1x + 2y - 50z >= 0

You should find the maximum number of statements that could be true at the same time given that x, y, and z are positive real numbers and x >= y >= z. As for the following example, the answer is 3.

Please help me with the idea or the design paradigm I should use to solve this problem. The algorithm should be relatively fast. It should be able to compute k = 1,000 in 1 seconds.

$\endgroup$
  • $\begingroup$ If you say "could" be true, do you mean for a given set of equations or in general? In a general case all given in-equations could be true so the answer is k. For k > 3 you have an over-determined system of inequations for which an infinite number of solutions can exist. For a given set you have to check every single inequation if they are not related amongst each other, i.e. if you don't have any limitations or relations for a,b,c. $\endgroup$ – a_guest Mar 4 '15 at 15:03
  • $\begingroup$ What have you tried? What's the best solution you came up with? What facts do you know about linear programming? Have you read textbook descriptions of algorithms for linear programming? You should find the key facts and concepts you need to solve this problem in standard textbooks. Hint: do you know how the simplex algorithm works, and the proof why it is correct? Can you apply any of the key facts used in that proof to this problem? $\endgroup$ – D.W. Mar 4 '15 at 21:49
3
$\begingroup$

There is a $O(k^4)$ time algorithm that works by considering all possible subsets of three out of the $k$ inequalities, looking at the "intersection point" of those 3 inequalities, and counting how many of the inequalities that intersection point satisfies.

In more detail:

This can be solved if you are familiar with some basic facts from linear programming and the simplex method. Let $S$ be a set of $m$ linear inequalities in $n$ variables. $S$ defines a $n$-dimensional polytope. Then the following fact is useful:

Fact: If $S$ has a feasible solution, then it has a feasible solution that is one of the vertices of the corresponding polytope.

(Recall that a vertex is a single point that is a "corner" of the polytope. Each vertex can be obtained by taking a subset of $n$ independent linear inequalities from $S$, converting them to equalities by changing $\ge$ to $=$, and solving to find the unique point at their intersection.)

For linear programming, a useful consequence of this fact is that, to find the optimal value of the objective function, it suffices to enumerate only the vertices of the polytope and compute the objective function for each such point. Here we have no objective function and care only about feasibility, but this basic fact is still useful.

In particular, in your problem we have $n=3$ variables ($x,y,z$) and we want to find the largest possible subset of the inequalities, say $j$ of them, that are all consistent. Any such subset of $j$ of the given inequalities corresponds to a set $S$ of $m=j+5$ inequalities: namely, the subset of $j$ inequalities, plus the additional inequalities $x\ge 0$, $y\ge 0$, $z \ge 0$, $x \ge y$, $y \ge z$. In this way we get a set $S$ of $m=j+5$ inequalities on $n=3$ variables. Now if there is a feasible solution to $S$, then one of the vertices of $S$ must be a feasible solution.

Essentially, this means that we can restrict our attention to only the vertices; we can ignore all other points in the polytope.

Of course, we don't know what $S$ is, so we don't know what the polytope is. Nonetheless, we can still use this fact. This fact means that we can restrict our attention to only the "possible vertices", where a "possible vertex" is a point that is a vertex of one such polytope. In other words, consider all possible polytopes obtained by taking some subset of the given inequalities and adding the additional inequalities $x\ge 0$, $y\ge 0$, $z \ge 0$, $x \ge y$, $y \ge z$; take the union of the vertices of all of these polytopes. Then it suffices to look only at these possible vertices -- we don't need to consider any other possible value of $x,y,z$.

How many possible vertices are there? Well, each vertex is determined by choosing $n=3$ of the inequalities, converting them to equalities, and looking at their intersection. So, there are only ${k+5 \choose 3} = O(k^3)$ possible vertices. For each possible vertex, we can count how many of the $k$ inequalities it satisfies, and see which one satisfies the largest number of inequalities. That one will be the optimal solution to your problem.

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