Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F19%3A00332584" target="_blank" >RIV/68407700:21230/19:00332584 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1137/17M1142922" target="_blank" >https://doi.org/10.1137/17M1142922</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/17M1142922" target="_blank" >10.1137/17M1142922</a>
Alternative languages
Result language
angličtina
Original language name
Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program
Original language description
We show that the general linear programming (LP) problem reduces in nearly linear time to the LP relaxations of many classical NP-hard combinatorial problems, assuming sparse encoding of instances. We distinguish two types of such reductions. In the first type (shown for set cover/packing, facility location, maximum satisfiability, maximum independent set, and multiway cut), the input linear program is feasible and bounded iff the optimum value of the LP relaxation attains a threshold, and then optimal solutions to the input linear program correspond to optimal solutions to the LP relaxation. In the second type (shown for exact set cover, three-dimensional matching, and constraint satisfaction), feasible solutions to the input linear program correspond to feasible solutions to the LP relaxations. Thus, the reduction preserves objective values of all (not only optimal) solutions. In polyhedral terms, every polytope in standard form is a scaled coordinate projection of the optimal or feasible set of the LP relaxation. Besides nearly linear-time reductions, we show that the considered LP relaxations are P-complete under log-space reductions, and therefore also hard to parallelize. These results pose a limitation on designing algorithms to compute exact or even approximate solutions to the LP relaxations, as any lower bound on the complexity of solving the general LP problem is inherited by the LP relaxations.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
SIAM JOURNAL ON OPTIMIZATION
ISSN
1052-6234
e-ISSN
1095-7189
Volume of the periodical
29
Issue of the periodical within the volume
3
Country of publishing house
US - UNITED STATES
Number of pages
27
Pages from-to
1745-1771
UT code for WoS article
000487929500001
EID of the result in the Scopus database
2-s2.0-85073702277