All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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