Linear vs. semidefinite extended formulations
From MaRDI portal
Recommendations
- The extended semidefinite linear complementarity problem: A reformulation approach
- A Lagrangian relaxation view of linear and semidefinite hierarchies
- scientific article; zbMATH DE number 1066345
- Lower bounds on the size of semidefinite programming relaxations
- An exact duality theory for semidefinite programming and its complexity implications
- Bounds on linear PDEs via semidefinite optimization
- On semidefinite linear complementarity problems
- Semidefinite optimization estimating bounds on linear functionals defined on solutions of linear ODEs
- Explicit solutions for interval semidefinite linear programs
- scientific article; zbMATH DE number 1985305
Cited in
(88)- Expressing combinatorial optimization problems by linear programs
- The matching problem has no small symmetric SDP
- The parity Hamiltonian cycle problem
- Maximum semidefinite and linear extension complexity of families of polytopes
- Decomposition techniques applied to the clique-stable set separation problem
- Affine reductions for LPs and SDPs
- Rational and real positive semidefinite rank can be different
- Algorithms for positive semidefinite factorization
- Factoring a band matrix over a semiring
- New limits of treewidth-based tractability in optimization
- A variational principle for ground spaces
- On \(\epsilon\)-sensitive monotone computations
- Lifts of non-compact convex sets and cone factorizations
- Nonnegative rank depends on the field
- \(k\)-neighborly faces of the Boolean quadric polytopes
- The common face of some 0/1-polytopes with NP-complete nonadjacency relation
- Extended formulations for radial cones
- A short proof that the extension complexity of the correlation polytope grows exponentially
- An upper bound for nonnegative rank
- A generalization of extension complexity that captures P
- The simplest families of polytopes associated with NP-hard problems
- The rectangle covering number of random Boolean matrices
- Some \(0/1\) polytopes need exponential size extended formulations
- A note on the extension complexity of the knapsack polytope
- Polynomial size IP formulations of knapsack may require exponentially large coefficients
- Clique-stable set separation in perfect graphs with no balanced skew-partitions
- Rank functions of tropical matrices
- Quantum learning of classical stochastic processes: the completely positive realization problem
- A comprehensive analysis of polyhedral lift-and-project methods
- Exponential lower bounds for polytopes in combinatorial optimization
- Mixed integer linear programming formulation techniques
- The parity Hamiltonian cycle problem in directed graphs
- Heuristics for exact nonnegative matrix factorization
- Deciding polyhedrality of spectrahedra
- Extended formulation lower bounds via hypergraph coloring?
- Average case polyhedral complexity of the maximum stable set problem
- Nondeterministic communication complexity of random Boolean functions (extended abstract)
- Tropical lower bound for extended formulations. II: Deficiency graphs of matrices
- Global completability with applications to self-consistent quantum tomography
- Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices
- Extended formulations for independence polytopes of regular matroids
- Common information and unique disjointness
- Query complexity in expectation
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Average case polyhedral complexity of the maximum stable set problem
- Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
- Polytopes of minimum positive semidefinite rank
- Clique versus independent set
- scientific article; zbMATH DE number 1066345 (Why is no real title available?)
- On the nonnegative rank of distance matrices
- Matrices of bounded psd rank are easy to detect
- The nonnegative rank of a matrix: hard problems, easy solutions
- Monotone projection lower bounds from extended formulation lower bounds
- A separation between tropical matrix ranks
- On the Power of Symmetric Linear Programs
- Cutting planes from extended LP formulations
- Regular matroids have polynomial extension complexity
- Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
- On the linear extension complexity of regular n-gons
- Approximate tensor decompositions: disappearance of many separations
- The slack realization space of a polytope
- On the \({\mathcal {H}}\)-free extension complexity of the TSP
- Forbidden vertices
- The complexity of positive semidefinite matrix factorization
- Positive semidefinite rank and nested spectrahedra
- An almost optimal algorithm for computing nonnegative rank
- A Polyhedral Characterization of Border Bases
- Deriving compact extended formulations via LP-based separation techniques
- Extended formulations in combinatorial optimization
- Deriving compact extended formulations via LP-based separation techniques
- Lifts for Voronoi cells of lattices
- Shadows of Newton polytopes
- Self-Dual Polyhedral Cones and Their Slack Matrices
- Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
- Restricted hidden cardinality constraints in causal models
- Rock extensions with linear diameters
- On the power of symmetric linear programs
- A topological version of Schaefer's dichotomy theorem
- Convexification techniques for fractional programs
- Hard submatrices for non-negative rank and communication complexity
- On the nonnegative ranks of matrices in Puiseux series fields
- Determining inscribability of polytopes via rank minimization based on slack matrices
- Time lower bounds for the Metropolis process and simulated annealing
- Smallest compact formulation for the permutahedron
- 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
This page was built for publication: Linear vs. semidefinite extended formulations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5415468)
