Maximizing the minimum load: the cost of selfishness

DOI10.1016/J.TCS.2013.02.033zbMATH Open1291.90090OpenAlexW4206158564MaRDI QIDQ390908FDOQ390908

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

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

zbMATH Keywords

schedulingprice of anarchymachine coveringenvy-ratio

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cites Work

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

Cited In (15)

• On the price of anarchy of two-stage machine scheduling games
• Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy
• Inefficiency of equilibria for the machine covering game on uniform machines
• Maximizing the minimum load for selfish agents
• Symmetry exploitation for online machine covering with bounded migration
• Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines
• The cost of selfishness for maximizing the minimum load on uniformly related machines
• The calculus of selfishness.
• On the sequential price of anarchy of isolation games
• Selfish load balancing
• Coordination mechanisms for scheduling games with proportional deterioration
• Maximizing the Minimum Load for Selfish Agents
• Tight Bounds for Selfish and Greedy Load Balancing
• 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)