Matroid matching

DOI10.1145/1806689.1806741zbMath1293.05035OpenAlexW2027229272MaRDI QIDQ2875164

Jan Vondrák, Jon Lee, M. I. Sviridenko

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1806689.1806741

zbMATH Keywords

matchinglocal searchmatroidSherali-Adams hierarchy

Mathematics Subject Classification ID

Hypergraphs (05C65) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Approximation algorithms (68W25)

Related Items (5)

Submodular Stochastic Probing on Matroids ⋮ Lower bounds for the Chvàtal-Gomory rank in the 0/1 cube ⋮ Inequalities on submodular functions via term rewriting ⋮ A simple PTAS for weighted matroid matching on strongly base orderable matroids ⋮ A simple PTAS for Weighted Matroid Matching on Strongly Base Orderable Matroids

This page was built for publication: Matroid matching