# Daniel Průša presents LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP

On 2017-12-19 11:00
at G205, Karlovo náměstí 13, Praha 2

NP-hard problems in combinatorial optimization can usually be expressed as 0-1

linear programs with natural linear programming (LP) relaxations. Solutions to

these relaxations are useful for computing exact optimal solutions (by

branch-and-bound methods using the LP relaxation to compute lower bounds),

approximate solutions (by rounding schemes), or exact optimal solutions for

tractable problem subclasses (those with zero integrality gap). Although the LP

relaxation can be solved in polynomial time, solving it for large-scale

instances can be inefficient or impossible.

We show that there are several NP-hard problems (constraint satisfaction,

multiway cut, set cover, maximum independent set, maximum satisfiability) whose

LP relaxations are as hard as solving the general LP problem. Precisely, the

general LP can be reduced in linear time to the LP relaxation of each of these

problems. This result poses a fundamental limitation for designing efficient

algorithms to solve the LP relaxations, because finding such an algorithm might

improve the complexity of best known algorithms for general LP.

linear programs with natural linear programming (LP) relaxations. Solutions to

these relaxations are useful for computing exact optimal solutions (by

branch-and-bound methods using the LP relaxation to compute lower bounds),

approximate solutions (by rounding schemes), or exact optimal solutions for

tractable problem subclasses (those with zero integrality gap). Although the LP

relaxation can be solved in polynomial time, solving it for large-scale

instances can be inefficient or impossible.

We show that there are several NP-hard problems (constraint satisfaction,

multiway cut, set cover, maximum independent set, maximum satisfiability) whose

LP relaxations are as hard as solving the general LP problem. Precisely, the

general LP can be reduced in linear time to the LP relaxation of each of these

problems. This result poses a fundamental limitation for designing efficient

algorithms to solve the LP relaxations, because finding such an algorithm might

improve the complexity of best known algorithms for general LP.

External WWW: http://epubs.siam.org/doi/pdf/10.1137/1.9781611974782.89