A lower bound for scheduling mechanisms

DOI10.1007/s00453-008-9165-3zbMath1183.68105OpenAlexW3136264843MaRDI 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 boundalgorithmic mechanism designscheduling unrelated machines

Mathematics Subject Classification ID

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

Related Items (19)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: A lower bound for scheduling mechanisms