Strong Reductions for Extended Formulations

Gábor Braun, Sebastian Pokutta, Aurko Roy

Type: Book-Chapter

Publication Date: 2016-01-01

Citations: 5

DOI: https://doi.org/10.1007/978-3-319-33461-5_29

Similar Works

Action	Title	Year	Authors
+	Lecture 12: Lower bounds on extended formulations	2015	Yuri Faenza Jakub Tarnawski
+ PDF Chat	Circuits in extended formulations	2024	Steffen Borgwardt Matthias Brugger
+	Splitting theorems and strong reductions	2019	Shaoyi Wang
+	Extension Theorems	1974	Roland Fraïssé
+	Extension theorems	1986	Jaroslav Lukeš Jan Malý Luděk Zajı́ček
+	Optimal Reductions: Further Results	2019	Jean Pierre Florens Michel Mouchart Jean‐Marie Rolin
+	The lifting and generalized extension problems	1969	Eduardo Ramon Bastida
+	Linear programming and Extensions	2014	Priyam Sharma
+	Linear Programming and Extensions	2000	Piercar Nicola
+	Linear Programming and Extensions	1963	George B. Dantzig
+	Linear Programming and Extensions	1964	Richard Coppins Nesa L’abbe Wu
+ PDF Chat	Algorithmic Solvability of the Lifting-Extension Problem	2017	Martin Čadek Marek Krčál Lukáš Vokřínek
+	Higher order interpretations for Basic Feasible Functions	2015	Emmanuel Hainry Romain Péchoux
+	Disjunctive Programming and Extended Formulations	2018	Egon Balas
+ PDF Chat	Approximations and Reductions	1894	A. Lodge
+	Weak and Weakened Weak Formulations	2013
+	Strong liftings	1969	A. Ionescu Tulcea C. Ionescu Tulcea
+	Complete problems and strong polynomial reducibilities	2005	K. Ganesan Steven Homer
+	Linear Programming and Extensions.	1964	S. Vajda George B. Dantzig
+	Linear Programming and Extensions.	1965	A. G. Azpeitia G. B. Dantzig

Action	Title	Year	Authors
+ PDF Chat	Limitations of Semidefinite Programs for Separable States and Entangled Games	2019	Aram W. Harrow Anand Natarajan Xiaodi Wu
+	Hierarchical Clustering via Spreading Metrics	2016	Aurko Roy Sebastian Pokutta
+ PDF Chat	Affine reductions for LPs and SDPs	2018	Gábor Braun Sebastian Pokutta Daniel Zink
+	Integer programming techniques for Polynomial Optimization	2017	Gonzalo Muñoz
+ PDF Chat	New limits of treewidth-based tractability in optimization	2020	Yuri Faenza Gonzalo Muñoz Sebastian Pokutta

Action	Title	Year	Authors
+	The stable set problem and the lift-and-project ranks of graphs	2003	L�szl� Lipt�k Levent Tun�el
+	Approximate Lasserre Integrality Gap for Unique Games	2010	Subhash Khot Preyas Popat Rishi Saket
+	On the Power of Symmetric LP and SDP Relaxations	2014	James R. Lee Prasad Raghavendra David Steurer Ning Tan
+ PDF Chat	Lower Bounds on the Size of Semidefinite Programming Relaxations	2015	James R. Lee Prasad Raghavendra David Steurer
+ PDF Chat	The matching polytope has exponential extension complexity	2014	Thomas Rothvoß
+	Approximate Constraint Satisfaction Requires Large LP Relaxations	2013	Siu On Chan James R. Lee Prasad Raghavendra David Steurer
+ PDF Chat	Approximation Limits of Linear Programs (Beyond Hierarchies)	2012	Gábor Braun Samuel Fiorini Sebastian Pokutta David Steurer
+	Inapproximability of Combinatorial Problems via Small LPs and SDPs	2015	Gábor Braun Sebastian Pokutta Daniel Zink
+	Linear vs. semidefinite extended formulations	2012	Samuel Fiorini Serge Massar Sebastian Pokutta Hans Raj Tiwary Ronald de Wolf
+	The matching polytope does not admit fully-polynomial size relaxation schemes	2014	Gábor Braun Sebastian Pokutta