Expressing combinatorial optimization problems by linear programs

DOI10.1016/0022-0000(91)90024-YzbMath0748.90074DBLPjournals/jcss/Yannakakis91WikidataQ56084006 ScholiaQ56084006MaRDI QIDQ1186549

Mihalis Yannakakis

Publication date: 28 June 1992

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

travelling salesmanmatching problemsymmetric linear programtransformation of polytopes

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Combinatorial optimization (90C27)

Related Items (only showing first 100 items - show all)

Slack Ideals in Macaulay2 ⋮ Nonnegative Matrix Factorization Requires Irrationality ⋮ Lifting for Simplicity: Concise Descriptions of Convex Sets ⋮ Query Complexity in Expectation ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies ⋮ Low-Sensitivity Functions from Unambiguous Certificates. ⋮ Deterministic Communication vs. Partition Number ⋮ Regular Matroids Have Polynomial Extension Complexity ⋮ Extension complexity of low-dimensional polytopes ⋮ On the extension complexity of scheduling polytopes ⋮ Bounds on the number of 2-level polytopes, cones, and configurations ⋮ Matrices of Bounded Psd Rank are Easy to Detect ⋮ Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes ⋮ Extended formulations for matroid polytopes through randomized protocols ⋮ Binary scalar products ⋮ Lifts for Voronoi cells of lattices ⋮ An extended formulation for the 1‐wheel inequalities of the stable set polytope ⋮ The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions ⋮ Shadows of Newton polytopes ⋮ Complex psd-minimal polytopes in dimensions two and three ⋮ The Complexity of Positive Semidefinite Matrix Factorization ⋮ Self-Dual Polyhedral Cones and Their Slack Matrices ⋮ The role of rationality in integer-programming relaxations ⋮ A deterministic parallel reduction from weighted matroid intersection search to decision ⋮ Polytope compatibility—From quantum measurements to magic squares ⋮ Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes ⋮ On the extension complexity of polytopes separating subsets of the Boolean cube ⋮ On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones ⋮ Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022 ⋮ A polyhedral perspective on tropical convolutions ⋮ On the binary and Boolean rank of regular matrices ⋮ Tensor decompositions on simplicial complexes with invariance ⋮ Combining realization space models of polytopes ⋮ Query-to-Communication Lifting for BPP ⋮ Extension Complexity of Independent Set Polytopes ⋮ Positive semidefinite rank and nested spectrahedra ⋮ Unnamed Item ⋮ On the Non-deterministic Communication Complexity of Regular Languages ⋮ Unnamed Item ⋮ Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract) ⋮ Mixed states in one spatial dimension: Decompositions and correspondence with nonnegative matrices ⋮ Parameterized Low-Rank Binary Matrix Approximation ⋮ Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz ⋮ Uniqueness of Nonnegative Matrix Factorizations by Rigidity Theory ⋮ Constructing Extended Formulations from Reflection Relations ⋮ Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time ⋮ Extended formulations in combinatorial optimization ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ ON THE NON-DETERMINISTIC COMMUNICATION COMPLEXITY OF REGULAR LANGUAGES ⋮ An Almost Optimal Algorithm for Computing Nonnegative Rank ⋮ Extended formulations in combinatorial optimization ⋮ Unnamed Item ⋮ The Slack Realization Space of a Polytope ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ A new integer programming formulation of the graphical traveling salesman problem ⋮ Mixed Integer Linear Programming Formulation Techniques ⋮ Extended formulations from communication protocols in output-efficient time ⋮ A new integer programming formulation of the graphical traveling salesman problem ⋮ Opposite Elements in Clutters ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Computing a Nonnegative Matrix Factorization---Provably ⋮ Low-Rank Approximation and Completion of Positive Tensors ⋮ The Parity Hamiltonian Cycle Problem in Directed Graphs ⋮ On Vertices and Facets of Combinatorial 2-Level Polytopes ⋮ Sum-of-Squares Rank Upper Bounds for Matching Problems ⋮ Extension Complexity of Polytopes with Few Vertices or Facets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Communication Complexity of Pairs of Graph Families with Applications ⋮ Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results ⋮ Tropical lower bound for extended formulations. II. Deficiency graphs of matrices ⋮ Forbidden Vertices ⋮ Common Information, Noise Stability, and Their Extensions ⋮ A comprehensive simplex-like algorithm for network optimization and perturbation analysis ⋮ On Polyhedral Approximations of the Positive Semidefinite Cone ⋮ Extended formulations for convex heptagons ⋮ Clique-stable set separation in perfect graphs with no balanced skew-partitions ⋮ Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond ⋮ The rectangle covering number of random Boolean matrices ⋮ Heuristics for exact nonnegative matrix factorization ⋮ Non-deterministic communication complexity with few witnesses ⋮ Sum-of-squares rank upper bounds for matching problems ⋮ Integrality gaps for strengthened linear relaxations of capacitated facility location ⋮ Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank ⋮ Some improved bounds on communication complexity via new decomposition of cliques ⋮ New formulations for the elementary shortest-path problem visiting a given set of nodes ⋮ Common information and unique disjointness ⋮ Matrices with high completely positive semidefinite rank ⋮ Sparse sums of squares on finite abelian groups and improved semidefinite lifts ⋮ Average case polyhedral complexity of the maximum stable set problem ⋮ Copositive matrices with circulant zero support set ⋮ Extension complexities of Cartesian products involving a pyramid ⋮ Excluding hooks and their complements ⋮ Polytopes of minimum positive semidefinite rank ⋮ Which semifields are exact? ⋮ The matching problem has no small symmetric SDP ⋮ On the combinatorial lower bound for the extension complexity of the spanning tree polytope ⋮ Clique versus independent set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Topics on perfect graphs
• The complexity of facets (and some facets of complexity)
• Lower bounds on monotone complexity of the logical permanent
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• The ellipsoid method and its consequences in combinatorial optimization
• Reducibility by algebraic projections
• On defining sets of vertices of the hypercube by linear inequalities
• Some simplified NP-complete graph problems
• Linear programming is log-space hard for P
• The perfectly matchable subgraph polytope of a bipartite graph
• Polyhedral Characterization of Discrete Dynamic Programming
• Odd Minimum Cut-Sets and b-Matchings
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: Expressing combinatorial optimization problems by linear programs