Santa Claus Meets Hypergraph Matchings

DOI10.1007/978-3-540-85363-3_2zbMath1159.68663OpenAlexW1578813712MaRDI QIDQ3541783

Arash Asadpour, Amin Saberi

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

Mathematics Subject Classification ID

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