A lower bound for scheduling mechanisms

DOI10.1007/s00453-008-9165-3zbMath1183.68105MaRDI QIDQ1031874

Elias Koutsoupias, Angelina Vidali, George Christodoulou

Publication date: 23 October 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9165-3

zbMATH Keywords

lower bound; algorithmic mechanism design; scheduling unrelated machines

Mathematics Subject Classification ID

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

Related Items

Unnamed Item, A new lower bound for deterministic truthful scheduling, Truthful mechanism design via correlated tree rounding, Distributed algorithmic mechanism design for scheduling on unrelated machines, The Pareto frontier of inefficiency in mechanism design, The price of envy-freeness in machine scheduling, Mechanisms for scheduling with single-bit private values, Setting lower bounds on truthfulness, Incentive compatible mechanisms for scheduling two-parameter job agents on parallel identical machines to minimize the weighted number of late jobs, No truthful mechanism can be better than \(n\) approximate for two natural problems, A lower bound of \(1+\varphi \) for truthful scheduling mechanisms, New bounds for truthful scheduling on two unrelated selfish machines, Mechanism design with a restricted action space, Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design, A Unified Approach to Truthful Scheduling on Related Machines, Recent Developments in the Mechanism Design Problem for Scheduling, The VCG Mechanism for Bayesian Scheduling

Cites Work

• Approximation algorithms for scheduling unrelated parallel machines
• Truthful mechanism design for multidimensional scheduling via cycle monotonicity
• Algorithmic mechanism design (extended abstract)
• Approximation techniques for utilitarian mechanism design
• Approximation algorithms for combinatorial auctions with complement-free bidders
• Optimal Auction Design
• Mechanism Design for Fractional Scheduling on Unrelated Machines
• Algorithms – ESA 2005
• STACS 2005
• Truthful randomized mechanisms for combinatorial auctions
• Algorithmic mechanism design
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item