Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program (Q5231683)
From MaRDI portal
scientific article; zbMATH DE number 7098587
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program |
scientific article; zbMATH DE number 7098587 |
Statements
Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program (English)
0 references
27 August 2019
0 references
linear programming relaxation
0 references
combinatorial optimization
0 references
nearly linear-time reduction
0 references
log-space reduction
0 references
convex polytope
0 references
universality
0 references
LP-completeness
0 references
extension complexity
0 references
0 references
