New bounds for truthful scheduling on two unrelated selfish machines

Olga Kuryatnikova, J. C. Vera

Research output: Contribution to journalArticleScientificpeer-review

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
JournalTheory of Computing Systems
DOIs
Publication statusE-pub ahead of print - May 2019

Fingerprint

Scheduling
Distribution functions
Rational functions

Keywords

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

Cite this

@article{a2c426423b9f41448462a985a64aba06,
title = "New bounds for truthful scheduling on two unrelated selfish machines",
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.",
keywords = "minimax optimization, truthful scheduling, approximation, piecewise functions, algorithmic mechanism design",
author = "Olga Kuryatnikova and Vera, {J. C.}",
year = "2019",
month = "5",
doi = "10.1007/s00224-019-09927-x",
language = "English",
journal = "Theory of Computing Systems",

}

New bounds for truthful scheduling on two unrelated selfish machines. / Kuryatnikova, Olga; Vera, J. C.

In: Theory of Computing Systems, 05.2019.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - New bounds for truthful scheduling on two unrelated selfish machines

AU - Kuryatnikova, Olga

AU - Vera, J. C.

PY - 2019/5

Y1 - 2019/5

N2 - 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.

AB - 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.

KW - minimax optimization

KW - truthful scheduling

KW - approximation

KW - piecewise functions

KW - algorithmic mechanism design

U2 - 10.1007/s00224-019-09927-x

DO - 10.1007/s00224-019-09927-x

M3 - Article

JO - Theory of Computing Systems

JF - Theory of Computing Systems

ER -