New bounds for truthful scheduling on two unrelated selfish machines

Olga Kuryatnikova, J.C. Vera

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)


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
Issue number2
Early online dateMay 2019
Publication statusPublished - Feb 2020


  • minimax optimization
  • truthful scheduling
  • approximation
  • piecewise functions
  • algorithmic mechanism design


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

Cite this