New bounds for truthful scheduling on two unrelated selfish machines

Olga Kuryatnikova*, Juan Carlos Vera Lizcano

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

Abstract

We consider the minimum makespan problem for n tasks and two unrelated parallel selfish machines. Let Rn be the best approximation ratio of randomized monotone scale-free algorithms. This class contains the most efficient algorithms known for truthful scheduling on two machines. We propose a new Min − Max formulation for Rn, as well as upper and lower bounds on Rn based on this formulation. For the lower bound, we exploit pointwise approximations of cumulative distribution functions (CDFs). For the upper bound, we construct randomized algorithms using distributions with piecewise rational CDFs. Our method improves upon the existing bounds on Rn for small n. In particular, we obtain almost tight bounds for n = 2 showing that |R2 − 1.505996| < 10− 6.
Original languageEnglish
Pages (from-to)199-226
Number of pages28
JournalTheory of Computing Systems
Volume64
Publication statusPublished - 30 May 2020
Externally publishedYes

Fingerprint

Dive into the research topics of 'New bounds for truthful scheduling on two unrelated selfish machines'. Together they form a unique fingerprint.

Cite this