A Unified Approach to Truthful Scheduling on Related Machines
From MaRDI portal
Publication:2800378
DOI10.1287/moor.2015.0730zbMath1353.68300arXiv1207.3523OpenAlexW2569519397MaRDI QIDQ2800378
Asaf Levin, Leah Epstein, Rob van Stee
Publication date: 15 April 2016
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1207.3523
Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)
Related Items (7)
Maximizing the minimum load: the cost of selfishness ⋮ Well-behaved online load balancing against strategic jobs ⋮ Mechanisms for scheduling with single-bit private values ⋮ Truthful mechanism design via correlated tree rounding ⋮ The cost of selfishness for maximizing the minimum load on uniformly related machines ⋮ A new lower bound for deterministic truthful scheduling ⋮ A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A truthful constant approximation for maximizing the minimum load on related machines
- Truthful mechanism design for multidimensional scheduling via cycle monotonicity
- Tighter approximation bounds for LPT scheduling in two special cases
- A lower bound for scheduling mechanisms
- Maximizing the minimum load for selfish agents
- Approximation schemes for scheduling on parallel machines
- A polynomial-time approximation scheme for maximizing the minimum machine completion time
- Approximation schemes for scheduling on uniformly related and identical parallel machines
- Approximation schemes for scheduling and covering on unrelated machines
- Truthful approximation mechanisms for scheduling selfish related machines
- A Deterministic Truthful PTAS for Scheduling Related Machines
- The Santa Claus problem
- Truthful Approximation Schemes for Single-Parameter Agents
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- Analysis of Greedy Solutions for a Replacement Part Sequencing Problem
- Optimal Auction Design
- Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation
- Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage Devices
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- Bounds for LPT Schedules on Uniform Processors
- All-norm approximation algorithms
- STACS 2004
- Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service
- Algorithms – ESA 2005
- Bounds for Certain Multiprocessing Anomalies
- Algorithmic mechanism design
This page was built for publication: A Unified Approach to Truthful Scheduling on Related Machines
