Extended formulations from communication protocols in output-efficient time

DOI10.1007/s10107-020-01535-9zbMath1458.94001arXiv1811.08529OpenAlexW3138640113MaRDI QIDQ5918910

Yuri Faenza, Manuel Aprile

Publication date: 28 August 2020

Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

perfect graphsextended formulationscommunication protocols

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Linear programming (90C05) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Communication theory (94A05) Perfect graphs (05C17)

Related Items (6)

Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond ⋮ Extended formulations for matroid polytopes through randomized protocols ⋮ The role of rationality in integer-programming relaxations ⋮ Unnamed Item ⋮ Extended formulations from communication protocols in output-efficient time ⋮ A tight approximation algorithm for the cluster vertex deletion problem

Cites Work

• Unnamed Item
• Unnamed Item
• Clique versus independent set
• Coloring perfect graphs with no balanced skew-partitions
• Extended formulations, nonnegative factorizations, and randomized communication protocols
• Expressing combinatorial optimization problems by linear programs
• On certain polytopes associated with graphs
• Extension complexity of stable set polytopes of bipartite graphs
• Min-up/min-down polytopes
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• On the Shannon capacity of a graph
• Disjunctive Programming
• Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits
• Extension Complexity of Independent Set Polytopes
• The Matching Polytope has Exponential Extension Complexity
• Communication Complexity
• No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ
• Linear vs. semidefinite extended formulations
• Some optimal inapproximability results
• Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
• Extended formulations in combinatorial optimization
• Extended formulations from communication protocols in output-efficient time

This page was built for publication: Extended formulations from communication protocols in output-efficient time