Santa Claus Meets Hypergraph Matchings

DOI10.1007/978-3-540-85363-3_2MaRDI QIDQ3541783zbMATH OpenOpenAlexFDO

Authors Arash Asadpour, Amin Saberi, Uriel Feige

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) Approximation algorithms (68W25) Combinatorial optimization (90C27) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Recommendations

• Santa claus meets hypergraph matchings
• A Tale of Santa Claus, Hypergraphs and Matroids
• On matchings in hypergraphs
• On a hypergraph matching problem
• The clique complex and hypergraph matching
• Matchings in hypergraphs of large minimum degree
• scientific article; zbMATH DE number 5763200
• Matchings and covers in hypergraphs
• Matching of given sizes in hypergraphs
• Pseudorandom hypergraph matchings

Cites work

• A condition for matchability in hypergraphs
• An improved approximation algorithm for combinatorial auctions with submodular bidders
• Approximation algorithms for scheduling unrelated parallel machines
• Hall's theorem for hypergraphs
• How easy is local search?
• scientific article; zbMATH DE number 5485443 (Why is no real title available?)
• scientific article; zbMATH DE number 5764783 (Why is no real title available?)
• scientific article; zbMATH DE number 5764883 (Why is no real title available?)
• scientific article; zbMATH DE number 1015852 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• On maximizing welfare when utility functions are subadditive
• Optimal approximation for the submodular welfare problem in the value oracle model
• The Santa Claus problem

Cited in

(12)

• Graph balancing: a special case of scheduling unrelated parallel machines
• Santa claus meets hypergraph matchings
• Nash social welfare, matrix permanent, and stable polynomials
• Polynomial-time perfect matchings in dense hypergraphs
• On the configuration-LP for scheduling on unrelated machines
• Finding independent transversals efficiently
• A geometric theory for hypergraph matching
• On the Keevash-Knox-Mycroft conjecture
• On min-max graph balancing with strict negative correlation constraints
• Matchings in multipartite hypergraphs
• On linear and semidefinite programming relaxations for hypergraph matching
• On the configuration LP for maximum budgeted allocation

This page was built for publication: Santa Claus Meets Hypergraph Matchings

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