Expressing combinatorial optimization problems by linear programs
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3976364 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3637614 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- scientific article; zbMATH DE number 3223737 (Why is no real title available?)
- A new polynomial-time algorithm for linear programming
- Linear programming is log-space hard for P
- Lower bounds on monotone complexity of the logical permanent
- Maximum matching and a polyhedron with 0,1-vertices
- Odd Minimum Cut-Sets and b-Matchings
- On defining sets of vertices of the hypercube by linear inequalities
- Optimization of a 532-city symmetric traveling salesman problem by branch and cut
- Polyhedral Characterization of Discrete Dynamic Programming
- Reducibility by algebraic projections
- Some simplified NP-complete graph problems
- The complexity of facets (and some facets of complexity)
- The ellipsoid method and its consequences in combinatorial optimization
- The perfectly matchable subgraph polytope of a bipartite graph
- Topics on perfect graphs
Cited in
(only showing first 100 items - show all)- Information-theoretic approximations of the nonnegative rank
- A geometric lower bound on the extension complexity of polytopes based on the f-vector
- On the complexity of computing a random Boolean function over the reals
- The role of rationality in integer-programming relaxations
- A deterministic parallel reduction from weighted matroid intersection search to decision
- Slack matrices, \(k\)-products, and 2-level polytopes
- The traveling salesman problem: a linear programming formulation
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- scientific article; zbMATH DE number 7559421 (Why is no real title available?)
- A counterexample to the Alon-Saks-Seymour conjecture and related problems
- Extended formulations for convex heptagons
- Clique-stable set separation in perfect graphs with no balanced skew-partitions
- Ordered biclique partitions and communication complexity problems
- Communication complexity of pairs of graph families with applications
- Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- A smaller extended formulation for the odd cycle inequalities of the stable set polytope
- Polytopes of minimum positive semidefinite rank
- Clique versus independent set
- Lifting for simplicity: concise descriptions of convex sets
- Which semifields are exact?
- Euclidean distance matrices and separations in communication complexity theory
- Nonnegative matrix factorization requires irrationality
- Small extended formulations for cyclic polytopes
- Circuits in extended formulations
- Learning semidefinite regularizers
- Tropical lower bound for extended formulations. II: Deficiency graphs of matrices
- The slack realization space of a polytope
- Algorithms for positive semidefinite factorization
- Extended formulations for polygons
- Linear algebraic methods in communication complexity
- Some improved bounds on communication complexity via new decomposition of cliques
- Recognizing Cartesian products of matrices and polytopes
- Linear programs for constraint satisfaction problems
- A combinatorial bound for linear programming and related problems
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- The complexity of positive semidefinite matrix factorization
- Extended formulations in combinatorial optimization
- Approximation of boolean functions by combinatorial rectangles
- scientific article; zbMATH DE number 6861975 (Why is no real title available?)
- A compact linear program for testing optimality of perfect matchings.
- Exponential lower bounds for polytopes in combinatorial optimization
- Refuting conjectures in extremal combinatorics via linear programming
- Projectively unique polytopes and toric slack ideals
- Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
- On the prize-collecting generalized minimum spanning tree problem
- Tropical lower bounds for extended formulations
- Worst-case results for positive semidefinite rank
- Extension complexities of Cartesian products involving a pyramid
- Heuristics for exact nonnegative matrix factorization
- Sum-of-squares rank upper bounds for matching problems
- Opposite elements in clutters
- The parity Hamiltonian cycle problem in directed graphs
- Extended formulations via decision diagrams
- Easy and optimal queries to reduce set uncertainty
- Low-rank approximation and completion of positive tensors
- On the nonnegative rank of distance matrices
- The common face of some 0/1-polytopes with NP-complete nonadjacency relation
- An analog of the Cook theorem for polytopes
- The matching problem has no small symmetric SDP
- Simulation theorems via pseudo-random properties
- Maximum semidefinite and linear extension complexity of families of polytopes
- On the linear extension complexity of regular \(n\)-gons
- Which nonnegative matrices are slack matrices?
- Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices
- A generalization of extension complexity that captures P
- Lifts for Voronoi cells of lattices
- Multiplicative updates for symmetric-cone factorizations
- On the extension complexity of scheduling polytopes
- Smallest compact formulation for the permutahedron
- Integrality gaps for strengthened linear relaxations of capacitated facility location
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- On the combinatorial lower bound for the extension complexity of the spanning tree polytope
- Symmetry Matters for Sizes of Extended Formulations
- Common information and unique disjointness
- Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
- Extension complexity of low-dimensional polytopes
- On the geometric interpretation of the nonnegative rank
- Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes
- Parameterized low-rank binary matrix approximation
- Hidden vertices in extensions of polytopes
- Sum-of-squares rank upper bounds for matching problems
- Sparktope: linear programs from algorithms
- Constructing extended formulations from reflection relations
- The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances
- Factoring a band matrix over a semiring
- A new integer programming formulation of the graphical traveling salesman problem
- A new integer programming formulation of the graphical traveling salesman problem
- The rectangle covering number of random Boolean matrices
- scientific article; zbMATH DE number 3908160 (Why is no real title available?)
- Slack ideals in Macaulay2
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- Positive semidefinite rank
- Uniqueness of Nonnegative Matrix Factorizations by Rigidity Theory
- Realizability of polytopes as a low rank matrix completion problem
- On the non-deterministic communication complexity of regular languages
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- Uncapacitated flow-based extended formulations
- Self-Dual Polyhedral Cones and Their Slack Matrices
- The nonnegative rank of a matrix: hard problems, easy solutions
This page was built for publication: Expressing combinatorial optimization problems by linear programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1186549)
