The Santa Claus problem
From MaRDI portal
Publication:2931367
DOI10.1145/1132516.1132522zbMATH Open1301.90057OpenAlexW1978593916MaRDI QIDQ2931367FDOQ2931367
Authors: N. Bansal, Maxim 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
Recommendations
Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Cited In (81)
- Fair-by-design matching
- Title not available (Why is that?)
- Approximating the Nash Social Welfare with Indivisible Items
- On the star decomposition of a graph: hardness results and approximation for the max-min optimization problem
- Inefficiency of equilibria for the machine covering game on uniform machines
- Maximizing the minimum load for selfish agents
- The price of fairness for indivisible goods
- Online-bounded analysis
- Nash Social Welfare, Matrix Permanent, and Stable Polynomials
- Santa Claus Meets Hypergraph Matchings
- Restricted max-min allocation: integrality gap and approximation algorithm
- Estimating the makespan of the two-valued restricted assignment problem
- Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
- Title not available (Why is that?)
- On \((1, \epsilon )\)-restricted max-min fair allocation problem
- A protocol for cutting matroids like cakes
- Min Sum Edge Coloring in Multigraphs Via Configuration LP
- The cost of selfishness for maximizing the minimum load on uniformly related machines
- General max-min fair allocation
- Integrality gaps for strengthened linear relaxations of capacitated facility location
- Maximizing Nash product social welfare in allocating indivisible goods
- An efficient polynomial time approximation scheme for load balancing on uniformly related machines
- Title not available (Why is that?)
- The hierarchical model for load balancing on two machines
- Approximation algorithms for computing maximin share allocations
- A unified approach to truthful scheduling on related machines
- Online bounded analysis
- Graph balancing: a special case of scheduling unrelated parallel machines
- Lazy Local Search Meets Machine Scheduling
- On the configuration LP for maximum budgeted allocation
- Strong LP formulations for scheduling splittable jobs on unrelated machines
- Finding a collective set of items: from proportional multirepresentation to group recommendation
- A constant-factor approximation for generalized malleable scheduling under \(M^\natural \)-concave processing speeds
- Semi-online machine covering for two uniform machines
- The efficiency of fair division
- A note on the integrality gap of the configuration LP for restricted Santa Claus
- Fair division of indivisible items between two players: design parameters for contested pile methods
- Multistage online maxmin allocation of indivisible entities
- The snowblower problem
- A new approach for bicriteria partitioning problem
- Two-player fair division of indivisible items: comparison of algorithms
- Online scheduling with rejection and reordering: exact algorithms for unit size jobs
- Fair and efficient allocation with few agent types, few item types, or small value levels
- On the configuration-LP for scheduling on unrelated machines
- Assigning sporadic tasks to unrelated machines
- Restricted Max-Min Fair Allocation
- Online scheduling with rejection and withdrawal
- Fair division of indivisible goods: recent progress and open questions
- Fair allocation of indivisible items with conflict graphs
- Setting lower bounds on truthfulness
- On-line machine covering on two machines with local migration
- Allocation of indivisible items with individual preference graphs
- On linear and semidefinite programming relaxations for hypergraph matching
- Contention resolution, matrix scaling and fair allocation
- A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation
- Maximizing the Minimum Load for Selfish Agents
- The price to pay for forgoing normalization in fair division of indivisible goods
- A truthful constant approximation for maximizing the minimum load on related machines
- Duplication monotonicity in the allocation of indivisible goods
- The snowblower problem
- Maximizing the minimum load: the cost of selfishness
- Fair Packing of Independent Sets
- A constant-factor approximation for generalized malleable scheduling under \(M^{\natural }\)-concave processing speeds
- Collective decision making
- A Quasi-Polynomial Approximation for the Restricted Assignment Problem
- Polynomial-time combinatorial algorithm for general max-min fair allocation
- Coalition formation in social environments with logic-based agents1
- Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
- Fair allocation algorithms for indivisible items under structured conflict constraints
- Online max-min fair allocation
- The existence of universally agreed fairest semi-matchings in any given bipartite graph
- Time-sharing scheduling with tolerance capacities
- Approximating Nash social welfare by matching and local search
- Better trees for Santa Claus
- Machine covering in the random-order model
- Allocating indivisible items with minimum dissatisfaction on preference graphs
- Minimizing and balancing envy among agents using ordered weighted average
- Resource time-sharing for IoT applications with deadlines
- Title not available (Why is that?)
- Compact LP Relaxations for Allocation Problems
- Maximin fair allocation of indivisible items under cost utilities
This page was built for publication: The Santa Claus problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931367)
