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

polyhedral combinatoricsfacetsseparatingcombinatorial optimization problemellipsoid methodfacial description

Mathematics Subject Classification ID

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

Cited in

(32)

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

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)