A New Lower Bound for Deterministic Truthful Scheduling
Giannakopoulos Y, Hammerl A, Poças D (2020)
Publication Type: Conference contribution, Original article
Publication year: 2020
Journal
Publisher: Springer Science and Business Media Deutschland GmbH
Book Volume: 12283 LNCS
Pages Range: 226-240
Conference Proceedings Title: Proceedings of the 13th Symposium on Algorithmic Game Theory (SAGT)
Event location: Augsburg
ISBN: 9783030579791
DOI: 10.1007/978-3-030-57980-7_15
Open Access Link: https://arxiv.org/abs/2005.10054
Abstract
We study the problem of truthfully scheduling m tasks to n selfish unrelated machines, under the objective of makespan minimization, as was introduced in the seminal work of Nisan and Ronen[NR99]. Closing the current gap of [2.618, n] on the approximation ratio of deterministic truthful mechanisms is a notorious open problem in the field of algorithmic mechanism design. We provide the first such improvement in more than a decade, since the lower bounds of 2.414 (for$$n=3$$) and 2.618 (for$$n\rightarrow \infty $$) by Christodoulou et al.[CKV07] and Koutsoupias and Vidali[KV07], respectively. More specifically, we show that the currently best lower bound of 2.618 can be achieved even for just$$n=4$$ machines; for$$n=5$$ we already get the first improvement, namely 2.711; and allowing the number of machines to grow arbitrarily large we can get a lower bound of 2.755.
Authors with CRIS profile
Involved external institutions
How to cite
APA:
Giannakopoulos, Y., Hammerl, A., & Poças, D. (2020). A New Lower Bound for Deterministic Truthful Scheduling. In Tobias Harks, Max Klimm (Eds.), Proceedings of the 13th Symposium on Algorithmic Game Theory (SAGT) (pp. 226-240). Augsburg, DE: Springer Science and Business Media Deutschland GmbH.
MLA:
Giannakopoulos, Yiannis, Alexander Hammerl, and Diogo Poças. "A New Lower Bound for Deterministic Truthful Scheduling." Proceedings of the 13th International Symposium on Algorithmic Game Theory, SAGT 2020, Augsburg Ed. Tobias Harks, Max Klimm, Springer Science and Business Media Deutschland GmbH, 2020. 226-240.
BibTeX: Download