A New Lower Bound for Deterministic Truthful Scheduling
Giannakopoulos Y, Hammerl A, Pocas D (2021)
Publication Language: English
Publication Type: Journal article, Original article
Publication year: 2021
Journal
Original Authors: Yiannis Giannakopoulos, Alexander Hammerl, Diogo Poças
DOI: 10.1007/s00453-021-00847-2
Open Access Link: https://rdcu.be/cm5XG
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 (in: The 31st Annual ACM symposium on Theory of Computing (STOC), 1999). 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→∞) by Christodoulou et al. (in: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007) and Koutsoupias and Vidali (in: Proceedings of Mathematical Foundations of Computer Science (MFCS), 2007), 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
University of Lisbon / Universidade de Lisboa (ULisboa)
Portugal (PT)
Technische Universität München (TUM)
Germany (DE)
Portugal (PT)
Technische Universität München (TUM)
Germany (DE)
How to cite
APA:
Giannakopoulos, Y., Hammerl, A., & Pocas, D. (2021). A New Lower Bound for Deterministic Truthful Scheduling. Algorithmica. https://dx.doi.org/10.1007/s00453-021-00847-2
MLA:
Giannakopoulos, Yiannis, Alexander Hammerl, and Diogo Pocas. "A New Lower Bound for Deterministic Truthful Scheduling." Algorithmica (2021).
BibTeX: Download