The Matching Problem Has No Fully Polynomial Size Linear Programming Relaxation Schemes

DOI10.1109/TIT.2015.2465864zbMath1359.68300OpenAlexW1594553832MaRDI QIDQ2977254

Gábor Braun, Sebastian Pokutta

Publication date: 28 April 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tit.2015.2465864

Mathematics Subject Classification ID

Linear programming (90C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (3)

The matching problem has no small symmetric SDP ⋮ The Frank-Wolfe algorithm: a short introduction ⋮ Three algorithms for graph locally harmonious colouring

This page was built for publication: The Matching Problem Has No Fully Polynomial Size Linear Programming Relaxation Schemes