Expressing combinatorial optimization problems by linear programs

From MaRDI portal

Publication:1186549

Jump to:navigation, search

DOI10.1016/0022-0000(91)90024-YzbMath0748.90074WikidataQ56084006 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 salesman matching problem symmetric linear program transformation 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

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, The parity Hamiltonian cycle problem, Approximate nonnegative rank is equivalent to the smooth rectangle bound, Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\), Lower bounds on the sizes of integer programs without additional variables, Simple extensions of polytopes, Approximation of boolean functions by combinatorial rectangles, Linear algebraic methods in communication complexity, On \(\epsilon\)-sensitive monotone computations, Maximum semidefinite and linear extension complexity of families of polytopes, Some \(0/1\) polytopes need exponential size extended formulations, A compact linear program for testing optimality of perfect matchings., On the nonnegative rank of distance matrices, Which nonnegative matrices are slack matrices?, Decomposition techniques applied to the clique-stable set separation problem, A counterexample to the Alon-Saks-Seymour conjecture and related problems, Affine reductions for LPs and SDPs, Some order dimension bounds for communication complexity problems, Parameterized low-rank binary matrix approximation, Lifts of non-compact convex sets and cone factorizations, Nonnegative rank depends on the field, Euclidean distance matrices and separations in communication complexity theory, Comment on ``Hypothesis testing by convex optimization, Learning semidefinite regularizers, Enumeration of 2-level polytopes, A smaller extended formulation for the odd cycle inequalities of the stable set polytope, A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector, On the linear extension complexity of regular \(n\)-gons, Some upper and lower bounds on PSD-rank, Easy and optimal queries to reduce set uncertainty, On the prize-collecting generalized minimum spanning tree problem, On the geometric interpretation of the nonnegative rank, An analog of the Cook theorem for polytopes, Polygons as sections of higher-dimensional polytopes, The multi-weighted Steiner tree problem: A reformulation by intersection, The common face of some 0/1-polytopes with NP-complete nonadjacency relation, Information-theoretic approximations of the nonnegative rank, Multipartite quantum correlation and communication complexities, Extended formulations for polygons, Completely positive semidefinite rank, Hidden vertices in extensions of polytopes, Simulation theorems via pseudo-random properties, Extended formulations for vertex cover, Algorithms for positive semidefinite factorization, The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances, Factoring a band matrix over a semiring, Strong reductions for extended formulations, Realizability of polytopes as a low rank matrix completion problem, Fitting tractable convex sets to support function evaluations, Smallest compact formulation for the permutahedron, Lower bounds on nonnegative rank via nonnegative nuclear norms, Tropical lower bounds for extended formulations, Extended formulations, nonnegative factorizations, and randomized communication protocols, On the extension complexity of combinatorial polytopes, On the existence of 0/1 polytopes with high semidefinite extension complexity, Uncapacitated flow-based extended formulations, Positive semidefinite rank, Worst-case results for positive semidefinite rank, Projectively unique polytopes and toric slack ideals, Recognizing Cartesian products of matrices and polytopes, Subdivided claws and the clique-stable set separation property, Pitch, extension complexity, and covering problems, Polynomial size linear programs for problems in \textsc{P}, Integer programming as a framework for optimization and approximability, The slack realization space of a matroid, Complements of unbounded convex polyhedra as polynomial images of \({{\mathbb{R}}}^n\), Lower bounds on matrix factorization ranks via noncommutative polynomial optimization, Worst-case analysis of clique MIPs, A new relaxation method for the generalized minimum spanning tree problem, A short proof that the extension complexity of the correlation polytope grows exponentially, An upper bound for nonnegative rank, Ordered biclique partitions and communication complexity problems, A generalization of extension complexity that captures P, Fooling-sets and rank, Approximate cone factorizations and lifts of polytopes, Small extended formulations for cyclic polytopes, New limits of treewidth-based tractability in optimization, Compact vs. exponential-size LP relaxations

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1186549&oldid=12051697"