I\'ve come across a programming question. I can\'t solve it but I can write the

Question

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.

Explanation / Answer

There is a O(k4) 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 ? 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?0, y?0, z?0, x?y, y?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?0, y?0, z?0, x?y, y?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+53)=O(k3) 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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.