Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture

DOI10.1002/rsa.21086zbMath1522.05336arXiv2011.07097OpenAlexW4224102625WikidataQ113913006 ScholiaQ113913006MaRDI QIDQ6077050

Nikhil Bansal, David G. Harris

Publication date: 17 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphmatchingiterative rounding

Mathematics Subject Classification ID

Hypergraphs (05C65) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Cites Work

• On the fractional matching polytope of a hypergraph
• On linear and semidefinite programming relaxations for hypergraph matching
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
• Algorithms to Approximate Column-sparse Packing Problems

This page was built for publication: Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture