0
$\begingroup$

Consider the following variant of linear programming, where we want to maximize the number of linear inequalities that are satisfied:

Input: linear inequalities $A_1x\le b_1$, ..., $A_nx \le b_n$; an integer $k$
Output: does there exist $x \in \mathbb{R}^d$ that satisfies at least $k$ of these linear inequalities?

To make the problem well-defined, we can assume everything is in $\mathbb{Q}$.

What is the complexity of this problem? It smells like it must surely be hard, but I cannot see how to prove it.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

Indeed, this is NP-hard. It is known as the maximum feasible subsystem problem (Max-FS). Max-FS is NP-hard. There is an approximation algorithm with approximation factor 2, but it does not admit a PTAS unless P=NP.

See

The Complexity and Approximability of Finding Maximum Feasible Subsystems of Linear Relations, Edoardo Amaldi and Viggo Kann. Theoretical computer science, 147(1-2), 1995, pp.181-210.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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