On designing truthful mechanisms for online scheduling

DOI10.1016/J.TCS.2008.12.057zbMATH Open1176.68036OpenAlexW2136543534MaRDI QIDQ838147FDOQ838147

Authors: V. Auletta, Roberto De Prisco, Paolo Penna, Giuseppe Persiano 

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

Recommendations

• Structural Information and Communication Complexity
• Automata, Languages and Programming
• On truthfulness and approximation for scheduling selfish tasks
• STACS 2004
• Truthful approximation mechanisms for scheduling selfish related machines

zbMATH Keywords

online algorithmsschedulingmechanism designonline truthful mechanisms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

• Truthful optimization using mechanisms with verification
• Truthful mechanism design for multidimensional scheduling via cycle monotonicity
• Fast payment schemes for truthful mechanisms with verification
• Algorithmic mechanism design
• Truthful auction for CPU time slots
• Decentralization and Mechanism Design for Online Machine Scheduling
• Structural Information and Communication Complexity
• Reducing truth-telling online mechanisms to online optimization
• Efficient mechanism design for online scheduling
• Mechanism design for decentralized online machine scheduling
• Automata, Languages and Programming
• Approximation and Online Algorithms

This page was built for publication: On designing truthful mechanisms for online scheduling

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