New bounds for truthful scheduling on two unrelated selfish machines

DOI10.1007/S00224-019-09927-XMaRDI QIDQ2300622zbMATH OpenOpenAlexWikidataFDO

Authors Olga Kuryatnikova, Juan Vera

Publication date 27 February 2020

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1711.04796

zbMATH Keywords

approximationalgorithmic mechanism designpiecewise functionsminimax optimizationtruthful scheduling

Mathematics Subject Classification ID

Randomized algorithms (68W20) Deterministic scheduling theory in operations research (90B35) Minimax problems in mathematical programming (90C47) Approximation algorithms (68W25)

Abstract: We consider the minimum makespan problem for $n$ tasks and two unrelated parallel selfish machines. Let $R_n$ 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 $R_n$, as well as upper and lower bounds on $R_n$ 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 $R_n$ for small $n$. In particular, we obtain almost tight bounds for $n=2$ showing that $|R_2-1.505996|<10^{-6}$.

Recommendations

• A new lower bound for deterministic truthful scheduling
• A new lower bound for deterministic truthful scheduling
• Randomized truthful algorithms for scheduling selfish tasks on parallel machines
• Randomized truthful algorithms for scheduling selfish tasks on parallel machines
• Truthful mechanisms for two-range-values variant of unrelated scheduling

Cites work

• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A Linear Programming Approach to the Cutting-Stock Problem
• A lower bound for scheduling mechanisms
• A lower bound of \(1+\varphi \) for truthful scheduling mechanisms
• Algorithmic mechanism design
• An improved randomized truthful mechanism for scheduling unrelated machines
• An introduction to copulas.
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Analysis of a linear programming heuristic for scheduling unrelated parallel machines
• Approximation algorithms for scheduling unrelated parallel machines
• Copula-based randomized mechanisms for truthful scheduling on two unrelated machines
• Exact and approximate truthful mechanisms for the shortest paths tree problem
• Exploiting symmetry in copositive programs via semidefinite hierarchies
• Mechanisms for scheduling with single-bit private values
• Reduction of symmetric semidefinite programs using the regular -representation
• Setting lower bounds on truthfulness (extended abstract)
• Symmetry groups, semidefinite programs, and sums of squares
• The Cutting-Plane Method for Solving Convex Programs
• Towards more practical linear programming-based techniques for algorithmic mechanism design
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Truthful mechanism design via correlated tree rounding

Cited in

(5)

• Truthful mechanisms for two-range-values variant of unrelated scheduling
• A new lower bound for deterministic truthful scheduling
• Copula-based randomized mechanisms for truthful scheduling on two unrelated machines
• Copula-based randomized mechanisms for truthful scheduling on two unrelated machines
• scientific article; zbMATH DE number 6297764 (Why is no real title available?)

Describes a project that uses

Uses Software

• WolframAlpha

This page was built for publication: New bounds for truthful scheduling on two unrelated selfish machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2300622)