On Linear Characterizations of Combinatorial Optimization Problems

DOI10.1137/0211053MaRDI QIDQ4742231zbMATH OpenOpenAlexFDO

Authors Richard Karp, Christos Papadimitriou

Publication date 1982

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/2b35e46ac8d010ab8c8bc9f913966bb0f484b3bc

zbMATH Keywords

combinatorial optimization problemellipsoid methodfacetsfacial descriptionpolyhedral combinatoricsseparating

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Nonlinear programming (90C30)

Cited in

(32)

• Bidimensional packing by bilinear programming
• Polyhedral proof methods in combinatorial optimization
• Probabilistic satisfiability
• The complexity of lifted inequalities for the knapsack problem
• On approximately fair cost allocation in Euclidean TSP games
• A polyhedral approach to sequence alignment problems
• Optimization with additional variables and constraints
• Facets and algorithms for capacitated lot sizing
• Valid inequalities and separation for mixed 0-1 constraints with variable upper bounds
• A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts
• Persistency of linear programming relaxations for the stable set problem
• A linear programming primer: from Fourier to Karmarkar
• Probabilistic existence of regular combinatorial structures
• Facet-defining inequalities for the simple graph partitioning polytope
• Valid inequalities and convex hulls for multilinear functions
• Complexity of column generation in network design with path-based survivability mechanisms
• Parameterized weighted containment
• Sensitivity theorems in integer linear programming
• The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization
• The branch and cut method for the clique partitioning problem
• Persistency of linear programming relaxations for the stable set problem
• The Boolean quadric polytope
• On the Composition of Convex Envelopes for Quadrilinear Terms
• Ranking functions for linear-constraint loops
• On cycle cones and polyhedra
• The ellipsoid method redux
• How to sell information optimally: an algorithmic study
• Facets of the clique partitioning polytope
• Recent trends in combinatorial optimization
• Optimizing over the subtour polytope of the travelling salesman problem
• Large-scale semidefinite programs in electronic structure calculation
• The stable set polytope of quasi-line graphs

This page was built for publication: On Linear Characterizations of Combinatorial Optimization Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4742231)