On Linear Characterizations of Combinatorial Optimization Problems
From MaRDI portal
Publication:4742231
DOI10.1137/0211053zbMath0505.65020OpenAlexW2018198126MaRDI QIDQ4742231
Christos H. Papadimitriou, Richard M. Karp
Publication date: 1982
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/2b35e46ac8d010ab8c8bc9f913966bb0f484b3bc
facetspolyhedral combinatoricscombinatorial optimization problemseparatingellipsoid methodfacial description
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Nonlinear programming (90C30)
Related Items
Polyhedral proof methods in combinatorial optimization, Persistency of Linear Programming Relaxations for the Stable Set Problem, Complexity of column generation in network design with path-based survivability mechanisms, The Boolean Quadric Polytope, Probabilistic satisfiability, A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts, Large-scale semidefinite programs in electronic structure calculation, Probabilistic existence of regular combinatorial structures, A linear programming primer: from Fourier to Karmarkar, On approximately fair cost allocation in Euclidean TSP games, Parameterized Weighted Containment, Sensitivity theorems in integer linear programming, On cycle cones and polyhedra, Facet-defining inequalities for the simple graph partitioning polytope, The stable set polytope of quasi-line graphs, The complexity of lifted inequalities for the knapsack problem, Unnamed Item, The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization, Optimization with additional variables and constraints, Bidimensional packing by bilinear programming, The Branch and Cut Method for the Clique Partitioning Problem, Facets of the clique partitioning polytope, Facets and algorithms for capacitated lot sizing, Valid inequalities and separation for mixed 0-1 constraints with variable upper bounds, On the Composition of Convex Envelopes for Quadrilinear Terms, Ranking Functions for Linear-Constraint Loops, Recent trends in combinatorial optimization, A polyhedral approach to sequence alignment problems, Optimizing over the subtour polytope of the travelling salesman problem, Persistency of linear programming relaxations for the stable set problem
