Portal de Periódicos da CAPES

A New Lower Bound for Deterministic Truthful Scheduling

2020; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-030-57980-7_15

1611-3349

Yiannis Giannakopoulos, Alexander Hammerl, Diogo Poças,

Imbalanced Data Classification Techniques

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.