Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program

DOI10.1137/17M1142922zbMath1429.68078WikidataQ127597422 ScholiaQ127597422MaRDI QIDQ5231683

Tomáš Werner, Daniel Průša

Publication date: 27 August 2019

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

zbMATH Keywords

combinatorial optimizationconvex polytopeuniversalitylinear programming relaxationextension complexitylog-space reductionLP-completenessnearly linear-time reduction

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Linear programming (90C05) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Super-reparametrizations of weighted CSPs: properties and optimization perspective

Uses Software

• MAXFLOW

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On quasilinear-time complexity theory
• Selected topics on assignment problems
• Smallest compact formulation for the permutahedron
• Approximating linear programming is log-space complete for P
• Parallel approximation algorithms by positive linear programming
• Monotonizing linear programs with up to two nonzeroes per column
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• One-third-integrality in the max-cut problem
• All 0-1 polytopes are traveling salesman polytopes
• Maximum Flows by Incremental Breadth-First Search
• Graphical Models, Exponential Families, and Variational Inference
• Two-Commodity Flow
• LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP
• Multiway cuts in node weighted graphs
• The Complexity of Valued Constraint Satisfaction Problems
• Reducibility among Combinatorial Problems
• A parallel approximation algorithm for positive linear programming
• The Power of Linear Programming for General-Valued CSPs
• A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
• Discrete-Variable Extremum Problems
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
• Extended formulations in combinatorial optimization
• Geometry of cuts and metrics

This page was built for publication: Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program