Expressing combinatorial optimization problems by linear programs
From MaRDI portal
The \({\mathcal P}={\mathcal NP}\) problem is investigated. The known \(\mathcal NP\)- complete problems can be formulated as an optimization of a linear function over a convex hull of feasible solutions of the problem. Such a representation does not provide an advantage because of the exponential size of the obtained linear program (LP). The paper aims at analysing the possibility to reduce the size of the LP. Adding new variables the author proposes to transform a polytope of the LP to a specific form, named symmetric. Roughly, it is a polytope that remains ``invariant under any permutation of the initial variables. The main result is that the travelling salesman problem and the matching problem cannot be expressed by any symmetric LP with a size less than exponential.
Recommendations
Cites work
- A new polynomial-time algorithm for linear programming
- 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?)
- 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)- Integer programming as a framework for optimization and approximability
- Linear programs for constraint satisfaction problems
- Non-deterministic communication complexity with few witnesses
- Approximation of boolean functions by combinatorial rectangles
- A compact linear program for testing optimality of perfect matchings.
- Compact vs. exponential-size LP relaxations
- Sum-of-squares rank upper bounds for matching problems
- Excluding hooks and their complements
- 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
- Euclidean distance matrices and separations in communication complexity theory
- Learning semidefinite regularizers
- Easy and optimal queries to reduce set uncertainty
- On the geometric interpretation of the nonnegative rank
- An analog of the Cook theorem for polytopes
- Completely positive semidefinite rank
- Hidden vertices in extensions of polytopes
- Extended formulations for vertex cover
- Algorithms for positive semidefinite factorization
- 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
- Refuting conjectures in extremal combinatorics via linear programming
- Information-theoretic approximations of the nonnegative rank
- Multipartite quantum correlation and communication complexities
- Factoring a band matrix over a semiring
- Fitting tractable convex sets to support function evaluations
- Recognizing Cartesian products of matrices and polytopes
- Subdivided claws and the clique-stable set separation property
- Pitch, extension complexity, and covering problems
- Worst-case analysis of clique MIPs
- New limits of treewidth-based tractability in optimization
- Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
- On \(\epsilon\)-sensitive monotone computations
- Parameterized low-rank binary matrix approximation
- Lifts of non-compact convex sets and cone factorizations
- Nonnegative rank depends on the field
- Polygons as sections of higher-dimensional polytopes
- The common face of some 0/1-polytopes with NP-complete nonadjacency relation
- Simulation theorems via pseudo-random properties
- The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances
- Projectively unique polytopes and toric slack ideals
- Compact linear programs for 2SAT
- Polynomial size linear programs for problems in \textsc{P}
- 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
- 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
- The rectangle covering number of random Boolean matrices
- Extension complexities of Cartesian products involving a pyramid
- Which semifields are exact?
- On the combinatorial lower bound for the extension complexity of the spanning tree polytope
- Approximate nonnegative rank is equivalent to the smooth rectangle bound
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- Some \(0/1\) polytopes need exponential size extended formulations
- Which nonnegative matrices are slack matrices?
- On the prize-collecting generalized minimum spanning tree problem
- The multi-weighted Steiner tree problem: A reformulation by intersection
- A new relaxation method for the generalized minimum spanning tree problem
- Some improved bounds on communication complexity via new decomposition of cliques
- Extended formulations for convex heptagons
- On the extension complexity of scheduling polytopes
- Bounds on the number of 2-level polytopes, cones, and configurations
- Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes
- Extended formulations for matroid polytopes through randomized protocols
- Clique-stable set separation in perfect graphs with no balanced skew-partitions
- Binary scalar products
- On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones
- On the binary and Boolean rank of regular matrices
- Combining realization space models of polytopes
- A comprehensive analysis of polyhedral lift-and-project methods
- Exponential lower bounds for polytopes in combinatorial optimization
- Mixed integer linear programming formulation techniques
- Nonnegative rank vs. binary rank
- Computing a nonnegative matrix factorization -- provably
- Low-rank approximation and completion of positive tensors
- The parity Hamiltonian cycle problem in directed graphs
- Sum-of-squares rank upper bounds for matching problems
- Extension complexity of polytopes with few vertices or facets
- Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap
- Heuristics for exact nonnegative matrix factorization
- Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes
- Nondeterministic communication complexity of random Boolean functions (extended abstract)
- Constructing extended formulations from reflection relations
- Integrality gaps for strengthened linear relaxations of capacitated facility location
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Tropical lower bound for extended formulations. II: Deficiency graphs of matrices
- New formulations for the elementary shortest-path problem visiting a given set of nodes
- Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices
- Extension complexity, MSO logic, and treewidth
- Common information and unique disjointness
- Query complexity in expectation
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)
