Lower bounds for approximating the matching polytope

zbMATH Open1410.90181arXiv1711.10145MaRDI QIDQ4607993FDOQ4607993

Authors: Makrand Sinha 

Publication date: 15 March 2018

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

Recommendations

• The matching polytope does not admit fully-polynomial size relaxation schemes
• The Matching Polytope has Exponential Extension Complexity
• The Matching Polytope has Exponential Extension Complexity
• Sherali-Adams relaxations of the matching polytope
• Polynomial size linear programs for problems in \textsc{P}

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cited In (4)

• The Matching Polytope has Exponential Extension Complexity
• The matching polytope does not admit fully-polynomial size relaxation schemes
• Pitch, extension complexity, and covering problems
• The Frank-Wolfe algorithm: a short introduction

This page was built for publication: Lower bounds for approximating the matching polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607993)