arbiter
JournalsPricingAccount

An improved bound for the price of anarchy for related machine scheduling

André Berger et al.

Discrete Optimization2025https://doi.org/10.1016/j.disopt.2025.100911article
AJG 2
Weight
0.37

What the paper says

In this paper, we introduce an improved upper bound for the efficiency of Nash equilibria in utilitarian scheduling games on related machines. The machines have varying speeds and adhere to the shortest processing time first policy. The goal of each job is to minimize its completion time, while the social objective is to minimize the sum of completion times. Our main finding establishes an upper bound of 2-1/(4m-2) on the price of anarchy for the general case of m machines. We improve this bound to 3/2 for the case of two machines, and to 2-1/(2 m) for the general case of m machines when the machines have divisible speeds, i.e., if the speed of each machine is divisible by the speed of any slower machine.

1 citation

Open paper page →

Cite this paper

https://doi.org/https://doi.org/10.1016/j.disopt.2025.100911

Or copy a formatted citation

@article{andré2025,
  title        = {{An improved bound for the price of anarchy for related machine scheduling}},
  author       = {André Berger et al.},
  journal      = {Discrete Optimization},
  year         = {2025},
  doi          = {https://doi.org/https://doi.org/10.1016/j.disopt.2025.100911},
}

Paste directly into BibTeX, Zotero, or your reference manager.

Flag this paper

An improved bound for the price of anarchy for related machine scheduling

Flags are reviewed by the Arbiter methodology team within 5 business days.

Evidence weight

0.37

Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40

F · citation impact0.16 × 0.4 = 0.06
M · momentum0.53 × 0.15 = 0.08
V · venue signal0.50 × 0.05 = 0.03
R · text relevance †0.50 × 0.4 = 0.20

† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.