Extended formulations, nonnegative factorizations, and randomized communication protocols

DOI10.1007/s10107-014-0755-3zbMath1356.90121arXiv1105.4127OpenAlexW1972982762WikidataQ114228503 ScholiaQ114228503MaRDI QIDQ745681

Samuel Fiorini, Hans Raj Tiwary, Roland Grappe, Yuri Faenza

Publication date: 14 October 2015

Published in: Lecture Notes in Computer Science, Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1105.4127

zbMATH Keywords

linear programmingcombinatorial optimizationmatrix factorizationextended formulationsnonnegative rankcommunication protocolsspecial polytopes

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Combinatorial optimization (90C27) Network protocols (68M12)

Related Items

Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond, Query Complexity in Expectation, Extended formulations for sparsity matroids, Common information and unique disjointness, Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes, Extended formulations for matroid polytopes through randomized protocols, On the combinatorial lower bound for the extension complexity of the spanning tree polytope, The role of rationality in integer-programming relaxations, Extension Complexity of Independent Set Polytopes, Fooling sets and the spanning tree polytope, Unnamed Item, A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”, Euclidean distance matrices and separations in communication complexity theory, Some upper and lower bounds on PSD-rank, On the \({\mathcal {H}}\)-free extension complexity of the TSP, Extended formulations for polygons, Subgraph polytopes and independence polytopes of count matroids, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Extended formulations from communication protocols in output-efficient time, On the existence of 0/1 polytopes with high semidefinite extension complexity, Uncapacitated flow-based extended formulations, Unnamed Item, Extension complexity of formal languages, Lower bounds on matrix factorization ranks via noncommutative polynomial optimization, Extended formulations of lower-truncated transversal polymatroids, A generalization of extension complexity that captures P

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Using separation algorithms to generate mixed integer model reformulations
• Expressing combinatorial optimization problems by linear programs
• On the distributional complexity of disjointness
• On the ratio of optimal integral and fractional covers
• Geometric algorithms and combinatorial optimization.
• Geometric arguments yield better bounds for threshold circuits and distributed computing
• On certain polytopes associated with graphs
• Combinatorial bounds on nonnegative rank and extended formulations
• The extremal function for complete minors
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Some \(0/1\) polytopes need exponential size extended formulations
• A linear-size zero?one programming model for the minimum spanning tree problem in planar graphs
• Quantum strategic game theory
• Symmetry Matters for the Sizes of Extended Formulations
• The Probabilistic Communication Complexity of Set Intersection
• Lectures on Polytopes
• Communication Complexity
• Linear vs. semidefinite extended formulations
• Maximum matching and a polyhedron with 0,1-vertices
• Matroids and the greedy algorithm
• Extended formulations in combinatorial optimization