A Lower Bound of 1 + φ for Truthful Scheduling Mechanisms

DOI10.1007/978-3-540-74456-6_41zbMath1147.90340OpenAlexW4235924339MaRDI QIDQ3525592

Angelina Vidali, Elias Koutsoupias

Publication date: 17 September 2008

Published in: Mathematical Foundations of Computer Science 2007 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74456-6_41

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (17)

Truthful mechanism design for multidimensional scheduling via cycle monotonicity ⋮ On designing truthful mechanisms for online scheduling ⋮ Approximation guarantee of OSP mechanisms: the case of machine scheduling and facility location ⋮ Scheduling without payments ⋮ Truthful optimization using mechanisms with verification ⋮ Improved lower bounds for non-utilitarian truthfulness ⋮ Mechanisms for scheduling with single-bit private values ⋮ Copula-based randomized mechanisms for truthful scheduling on two unrelated machines ⋮ A lower bound of \(1+\varphi \) for truthful scheduling mechanisms ⋮ Recent Developments in the Mechanism Design Problem for Scheduling ⋮ Optimal collusion-resistant mechanisms with verification ⋮ A new lower bound for deterministic truthful scheduling ⋮ Fast payment schemes for truthful mechanisms with verification ⋮ Unnamed Item ⋮ Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions ⋮ Bribeproof Mechanisms for Two-Values Domains ⋮ Truthful mechanisms for two-range-values variant of unrelated scheduling

This page was built for publication: A Lower Bound of 1 + φ for Truthful Scheduling Mechanisms