LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA16-05872S" target="_blank" >GA16-05872S: Pravděpodobnostní grafové modely a hluboké učení</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms

ISBN

978-1-61197-478-2

ISSN

—

e-ISSN

—

Počet stran výsledku

11

Strana od-do

1372-1382

Název nakladatele

Society for Industrial and Applied Mathematics

Místo vydání

Philadelphia, PA

Místo konání akce

Barcelona

Datum konání akce

16. 1. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—