The Santa Claus problem
From MaRDI portal
Publication:2931367
DOI10.1145/1132516.1132522zbMath1301.90057OpenAlexW1978593916MaRDI QIDQ2931367
Nikhil Bansal, M. I. Sviridenko
Publication date: 25 November 2014
Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1132516.1132522
Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (73)
Approximating the Nash Social Welfare with Indivisible Items ⋮ Online-bounded analysis ⋮ Fair Packing of Independent Sets ⋮ Approximation Algorithms for Computing Maximin Share Allocations ⋮ Integrality gaps for strengthened linear relaxations of capacitated facility location ⋮ Maximizing Nash product social welfare in allocating indivisible goods ⋮ Restricted max-min allocation: integrality gap and approximation algorithm ⋮ Finding a collective set of items: from proportional multirepresentation to group recommendation ⋮ Setting lower bounds on truthfulness ⋮ A constant-factor approximation for generalized malleable scheduling under \(M^\natural \)-concave processing speeds ⋮ A Protocol for Cutting Matroids Like Cakes ⋮ A truthful constant approximation for maximizing the minimum load on related machines ⋮ Maximizing the minimum load: the cost of selfishness ⋮ Multistage online maxmin allocation of indivisible entities ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Min Sum Edge Coloring in Multigraphs Via Configuration LP ⋮ Fair and efficient allocation with few agent types, few item types, or small value levels ⋮ Machine covering in the random-order model ⋮ Strong LP formulations for scheduling splittable jobs on unrelated machines ⋮ On the configuration LP for maximum budgeted allocation ⋮ Online max-min fair allocation ⋮ Resource time-sharing for IoT applications with deadlines ⋮ Fair division of indivisible goods: recent progress and open questions ⋮ Allocation of indivisible items with individual preference graphs ⋮ Polynomial-time combinatorial algorithm for general max-min fair allocation ⋮ The price to pay for forgoing normalization in fair division of indivisible goods ⋮ A note on the integrality gap of the configuration LP for restricted Santa Claus ⋮ General max-min fair allocation ⋮ Allocating indivisible items with minimum dissatisfaction on preference graphs ⋮ Minimizing and balancing envy among agents using ordered weighted average ⋮ A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation ⋮ Fair allocation of indivisible items with conflict graphs ⋮ Graph balancing: a special case of scheduling unrelated parallel machines ⋮ Fair-by-design matching ⋮ Compact LP Relaxations for Allocation Problems ⋮ Online scheduling with rejection and withdrawal ⋮ On the star decomposition of a graph: hardness results and approximation for the max-min optimization problem ⋮ An efficient polynomial time approximation scheme for load balancing on uniformly related machines ⋮ The hierarchical model for load balancing on two machines ⋮ Santa Claus Meets Hypergraph Matchings ⋮ A Quasi-Polynomial Approximation for the Restricted Assignment Problem ⋮ On-line machine covering on two machines with local migration ⋮ Fair division of indivisible items between two players: design parameters for contested pile methods ⋮ Coalition formation in social environments with logic-based agents1 ⋮ Duplication monotonicity in the allocation of indivisible goods ⋮ The price of fairness for indivisible goods ⋮ Online scheduling with rejection and reordering: exact algorithms for unit size jobs ⋮ On the configuration-LP for scheduling on unrelated machines ⋮ Restricted Max-Min Fair Allocation ⋮ Assigning sporadic tasks to unrelated machines ⋮ Estimating the makespan of the two-valued restricted assignment problem ⋮ The efficiency of fair division ⋮ Online Bounded Analysis ⋮ Unnamed Item ⋮ The cost of selfishness for maximizing the minimum load on uniformly related machines ⋮ Inefficiency of equilibria for the machine covering game on uniform machines ⋮ On linear and semidefinite programming relaxations for hypergraph matching ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Two-player fair division of indivisible items: comparison of algorithms ⋮ On \((1, \epsilon )\)-restricted max-min fair allocation problem ⋮ A Unified Approach to Truthful Scheduling on Related Machines ⋮ The existence of universally agreed fairest semi-matchings in any given bipartite graph ⋮ Maximizing the Minimum Load for Selfish Agents ⋮ Semi-online machine covering for two uniform machines ⋮ Lazy Local Search Meets Machine Scheduling ⋮ Nash Social Welfare, Matrix Permanent, and Stable Polynomials ⋮ Maximizing the minimum load for selfish agents ⋮ Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines ⋮ Contention resolution, matrix scaling and fair allocation ⋮ Unnamed Item ⋮ Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings ⋮ A new approach for bicriteria partitioning problem
This page was built for publication: The Santa Claus problem
