A new lower bound for deterministic truthful scheduling

DOI10.1007/s00453-021-00847-2OpenAlexW4205792258MaRDI QIDQ5918088

Diogo Poças, Alexander Hammerl, Yiannis Giannakopoulos

Publication date: 2 September 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2005.10054

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

The polyhedral geometry of truthful auctions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Truthful optimization using mechanisms with verification
• Approximation algorithms for scheduling unrelated parallel machines
• The Pareto frontier of inefficiency in mechanism design
• Truthful mechanism design for multidimensional scheduling via cycle monotonicity
• Copula-based randomized mechanisms for truthful scheduling on two unrelated machines
• The power of verification for one-parameter agents
• Truthful mechanisms for two-range-values variant of unrelated scheduling
• A lower bound for scheduling mechanisms
• Setting lower bounds on truthfulness
• Scheduling without payments
• A lower bound of \(1+\varphi \) for truthful scheduling mechanisms
• Optimal collusion-resistant mechanisms with verification
• New bounds for truthful scheduling on two unrelated selfish machines
• The anarchy of scheduling without money
• A Unified Approach to Truthful Scheduling on Related Machines
• Algorithmic mechanism design (extended abstract)
• A Deterministic Truthful PTAS for Scheduling Related Machines
• Optimal Lower Bounds for Anonymous Scheduling Mechanisms
• Truthful Approximation Schemes for Single-Parameter Agents
• The VCG Mechanism for Bayesian Scheduling
• A Lower Bound of 1 + φ for Truthful Scheduling Mechanisms
• On the Nisan-Ronen conjecture for submodular valuations
• Bayesian Truthful Mechanisms for Job Scheduling from Bi-criterion Approximation Algorithms
• Prior-independent mechanisms for scheduling
• A new lower bound for deterministic truthful scheduling
• Algorithmic mechanism design

This page was built for publication: A new lower bound for deterministic truthful scheduling