On designing truthful mechanisms for online scheduling

DOI10.1016/J.TCS.2008.12.057MaRDI QIDQ838147zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(12)

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

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)