LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F17%3A00311741" target="_blank" >RIV/68407700:21230/17:00311741 - isvavai.cz</a>
Result on the web
<a href="http://epubs.siam.org/doi/abs/10.1137/1.9781611974782.89" target="_blank" >http://epubs.siam.org/doi/abs/10.1137/1.9781611974782.89</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/1.9781611974782.89" target="_blank" >10.1137/1.9781611974782.89</a>
Alternative languages
Result language
angličtina
Original language name
LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP
Original language description
We show that solving linear programming (LP) relaxations of many classical NP-hard combinatorial optimization problems is 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 the general LP. Besides linear-time reductions, we show that the LP relaxations of the considered problems are P-complete under log-space reduction, therefore also hard to parallelize.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
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/GA16-05872S" target="_blank" >GA16-05872S: Probabilistic Graphical Models and Deep Learning</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2017
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
Article name in the collection
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
ISBN
978-1-61197-478-2
ISSN
—
e-ISSN
—
Number of pages
11
Pages from-to
1372-1382
Publisher name
Society for Industrial and Applied Mathematics
Place of publication
Philadelphia, PA
Event location
Barcelona
Event date
Jan 16, 2017
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—