Santa Claus Meets Hypergraph Matchings
From MaRDI portal
Publication:3541783
DOI10.1007/978-3-540-85363-3_2zbMath1159.68663OpenAlexW1578813712MaRDI QIDQ3541783
Publication date: 27 November 2008
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_2
Hypergraphs (05C65) Combinatorial optimization (90C27) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)
Related Items (8)
On the configuration LP for maximum budgeted allocation ⋮ Graph balancing: a special case of scheduling unrelated parallel machines ⋮ Polynomial-time perfect matchings in dense hypergraphs ⋮ On the configuration-LP for scheduling on unrelated machines ⋮ On linear and semidefinite programming relaxations for hypergraph matching ⋮ Finding independent transversals efficiently ⋮ Nash Social Welfare, Matrix Permanent, and Stable Polynomials ⋮ A geometric theory for hypergraph matching
Cites Work
- Approximation algorithms for scheduling unrelated parallel machines
- How easy is local search?
- A condition for matchability in hypergraphs
- The Santa Claus problem
- On maximizing welfare when utility functions are subadditive
- An improved approximation algorithm for combinatorial auctions with submodular bidders
- Hall's theorem for hypergraphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Santa Claus Meets Hypergraph Matchings