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)- Computing a nonnegative matrix factorization -- provably
- Approximate cone factorizations and lifts of polytopes
- Extension complexity of low-dimensional polytopes
- Comment on ``Hypothesis testing by convex optimization
- Recognizing Cartesian products of matrices and polytopes
- Extension complexity of polytopes with few vertices or facets
- Realizability of polytopes as a low rank matrix completion problem
- Average case polyhedral complexity of the maximum stable set problem
- Matrices with high completely positive semidefinite rank
- On the combinatorial lower bound for the extension complexity of the spanning tree polytope
- Solving linear optimization problems with max-star composition equation constraints
- Extended formulations for polygons
- Heuristics for exact nonnegative matrix factorization
- Approximation of boolean functions by combinatorial rectangles
- Small extended formulations for cyclic polytopes
- On the nonnegative rank of distance matrices
- Linear algebraic methods in communication complexity
- A combinatorial bound for linear programming and related problems
- Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time
- Information-theoretic approximations of the nonnegative rank
- Compact vs. exponential-size LP relaxations
- Exponential lower bounds for polytopes in combinatorial optimization
- Copositive matrices with circulant zero support set
- Extended formulations in combinatorial optimization
- An upper bound for nonnegative rank
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- Linear programs for constraint satisfaction problems
- Uncapacitated flow-based extended formulations
- Smallest compact formulation for the permutahedron
- The complexity of positive semidefinite matrix factorization
- Which nonnegative matrices are slack matrices?
- The multi-weighted Steiner tree problem: A reformulation by intersection
- Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
- A generalization of extension complexity that captures P
- Tropical lower bounds for extended formulations
- Worst-case results for positive semidefinite rank
- Tight lower bounds on the sizes of symmetric extensions of permutahedra and similar results
- Integrality gaps for strengthened linear relaxations of capacitated facility location
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Opposite elements in clutters
- Lifts of non-compact convex sets and cone factorizations
- An almost optimal algorithm for computing nonnegative rank
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- A short proof that the extension complexity of the correlation polytope grows exponentially
- On the geometric interpretation of the nonnegative rank
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- Multipartite quantum correlation and communication complexities
- Nonnegative rank depends on the field
- Mixed integer linear programming formulation techniques
- Some \(0/1\) polytopes need exponential size extended formulations
- Some upper and lower bounds on PSD-rank
- A new relaxation method for the generalized minimum spanning tree problem
- Polytopes of minimum positive semidefinite rank
- New formulations for the elementary shortest-path problem visiting a given set of nodes
- Learning semidefinite regularizers
- Extended formulations in combinatorial optimization
- A counterexample to the Alon-Saks-Seymour conjecture and related problems
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- Positive semidefinite rank
- Algorithms for positive semidefinite factorization
- Positive semidefinite rank and nested spectrahedra
- On the linear extension complexity of regular \(n\)-gons
- Extended formulations for convex heptagons
- Clique-stable set separation in perfect graphs with no balanced skew-partitions
- scientific article; zbMATH DE number 6861975 (Why is no real title available?)
- Hidden vertices in extensions of polytopes
- Non-deterministic communication complexity with few witnesses
- The traveling salesman problem: a linear programming formulation
- Common information and unique disjointness
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Clique versus independent set
- Extension complexity of independent set polytopes
- On the extension complexity of polytopes separating subsets of the Boolean cube
- Polygons as sections of higher-dimensional polytopes
- Constructing extended formulations from reflection relations
- Fooling-sets and rank
- scientific article; zbMATH DE number 2084733 (Why is no real title available?)
- The common face of some 0/1-polytopes with NP-complete nonadjacency relation
- Deterministic communication vs. partition number
- A comprehensive simplex-like algorithm for network optimization and perturbation analysis
- Subdivided claws and the clique-stable set separation property
- The parity Hamiltonian cycle problem in directed graphs
- A comprehensive analysis of polyhedral lift-and-project methods
- Euclidean distance matrices and separations in communication complexity theory
- New limits of treewidth-based tractability in optimization
- Communication complexity of pairs of graph families with applications
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- Some order dimension bounds for communication complexity problems
- An analog of the Cook theorem for polytopes
- A smaller extended formulation for the odd cycle inequalities of the stable set polytope
- Sum-of-squares rank upper bounds for matching problems
- Query-to-communication lifting for BPP
- scientific article; zbMATH DE number 3908160 (Why is no real title available?)
- Common Information, Noise Stability, and Their Extensions
- Simulation theorems via pseudo-random properties
- The slack realization space of a matroid
- The parity Hamiltonian cycle problem
- Extended formulations for matroid polytopes through randomized protocols
- On polyhedral approximations of the positive semidefinite cone
- The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances
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)
