How to sell hyperedges: the hypermatching assignment problem

DOI10.1137/1.9781611973105.25MaRDI QIDQ5741733zbMATH OpenOpenAlexFDO

Authors Marek Cygan, Fabrizio Grandoni, Monaldo Mastrolilli

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973105.25

Mathematics Subject Classification ID

Management decision making, including multiple objectives (90B50) Combinatorial optimization (90C27) Approximation algorithms (68W25) Hypergraphs (05C65) Production models (90B30)

Recommendations

• Generalized hypergraph matching via iterated packing and local ratio
• On linear and semidefinite programming relaxations for hypergraph matching
• scientific article; zbMATH DE number 6297805
• Tight approximation algorithms for maximum separable assignment problems
• On the configuration LP for maximum budgeted allocation

Cited in

(21)

• Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
• $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
• Understanding the correlation gap for matchings
• An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
• Approximation algorithms for the k^+-star packing problem
• Approximation algorithms for non-sequential star packing problems
• Approximate multi-matroid intersection via iterative refinement
• On maximum bipartite matching with separation
• The limits of local search for weighted \(k\)-set packing
• On the hardest problem formulations for the 0/1 Lasserre hierarchy
• An improved approximation algorithm for the maximum weight independent set problem in d-claw free graphs
• Sum-of-squares bounds via Boolean function analysis
• The limits of local search for weighted k-set packing
• Coupled and \(k\)-sided placements: generalizing generalized assignment
• scientific article; zbMATH DE number 7378399 (Why is no real title available?)
• An improved kernel for planar vertex-disjoint triangle packing
• Approximation algorithms for non-sequential star packing problems
• Perfect matching in bipartite hypergraphs subject to a demand graph
• Hardness of approximating bounded-degree max 2-CSP and independent set on k-claw-free graphs
• Generalized hypergraph matching via iterated packing and local ratio
• Generalized assignment of time-sensitive item groups

This page was built for publication: How to sell hyperedges: the hypermatching assignment problem

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