On designing truthful mechanisms for online scheduling

DOI10.1016/j.tcs.2008.12.057zbMath1176.68036OpenAlexW2136543534MaRDI QIDQ838147

Roberto De Prisco, Giuseppe Persiano, Paolo Penna, Vincenzo Auletta

Publication date: 21 August 2009

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

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

zbMATH Keywords

schedulingonline algorithmsmechanism designonline truthful mechanisms

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Truthful approximation mechanisms for scheduling selfish related machines
• Algorithmic mechanism design (extended abstract)
• Truthful Approximation Schemes for Single-Parameter Agents
• Tighter Approximation Bounds for LPT Scheduling in Two Special Cases
• A Lower Bound of 1 + φ for Truthful Scheduling Mechanisms
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Mechanism Design for Fractional Scheduling on Unrelated Machines
• Improved Lower Bounds for Non-utilitarian Truthfulness
• Automata, Languages and Programming
• Algorithms – ESA 2005
• Bounds for Certain Multiprocessing Anomalies