Maximizing the minimum load: the cost of selfishness

DOI10.1016/J.TCS.2013.02.033MaRDI QIDQ390908zbMATH OpenOpenAlexFDO

Authors Leah Epstein, Elena Kleiman, Rob van Stee, Xujin Chen

Publication date 9 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2013.02.033

zbMATH Keywords

schedulingprice of anarchymachine coveringenvy-ratio

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• The cost of selfishness for maximizing the minimum load on uniformly related machines
• Maximizing the Minimum Load for Selfish Agents
• Selfish load balancing
• Maximizing the minimum load for selfish agents
• The price of anarchy for utilitarian scheduling games on related machines

Cites work

• scientific article; zbMATH DE number 6678949 (Why is no real title available?)
• scientific article; zbMATH DE number 2038735 (Why is no real title available?)
• scientific article; zbMATH DE number 6472625 (Why is no real title available?)
• A linear time approximation algorithm for multiprocessor scheduling
• A performance guarantee for the greedy set-partitioning algorithm
• A unified approach to truthful scheduling on related machines
• Algorithmic mechanism design
• Approximation and Online Algorithms
• Bounds on Multiprocessing Timing Anomalies
• Convergence time to Nash equilibrium in load balancing
• How bad is selfish routing?
• Inefficiency of equilibria for the machine covering game on uniform machines
• Maximizing the minimum load for selfish agents
• Maximizing the minimum load: the cost of selfishness
• Non-cooperative games
• Performance guarantees of local search for multiprocessor scheduling
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• The Price of Stability for Network Design with Fair Cost Allocation
• The Santa Claus problem
• The cost of selfishness for maximizing the minimum load on uniformly related machines
• The price of selfish routing
• The structure and complexity of Nash equilibria for a selfish routing game
• Tight bounds for worst-case equilibria
• Truthful approximation schemes for single-parameter agents
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Worst-case equilibria

Cited in

(21)

• Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines
• Coordination mechanisms for scheduling games with proportional deterioration
• Maximizing the minimum load for selfish agents
• Inefficiency of equilibria for the machine covering game on uniform machines
• Reducing price of anarchy of selfish task allocation with more selfishness
• The price of anarchy for a berth allocation game
• Tight Bounds for Selfish and Greedy Load Balancing
• Symmetry exploitation for online machine covering with bounded migration
• Maximizing the Minimum Load for Selfish Agents
• Tighter price of anarchy for selfish task allocation on selfish machines
• Selfish load balancing
• The power of one evil secret agent
• Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy
• On the sequential price of anarchy of isolation games
• The calculus of selfishness.
• Tight bounds for selfish and greedy load balancing
• The power of one secret agent
• On the price of anarchy of two-stage machine scheduling games
• The cost of selfishness for maximizing the minimum load on uniformly related machines
• Inefficiency of Nash equilibrium for scheduling games with constrained jobs: a parametric analysis
• Maximizing the minimum load: the cost of selfishness

This page was built for publication: Maximizing the minimum load: the cost of selfishness

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