New bounds for truthful scheduling on two unrelated selfish machines

DOI10.1007/S00224-019-09927-XzbMATH Open1434.68678arXiv1711.04796OpenAlexW3101621606WikidataQ127783117 ScholiaQ127783117MaRDI QIDQ2300622FDOQ2300622

Authors: Olga Kuryatnikova, Juan Vera 

Publication date: 27 February 2020

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

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}$.

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

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

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)

Cites Work

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

Cited In (5)

• Truthful mechanisms for two-range-values variant of unrelated scheduling
• A new lower bound for deterministic truthful scheduling
• Title not available (Why is that?)
• Copula-based randomized mechanisms for truthful scheduling on two unrelated machines
• Copula-based randomized mechanisms for truthful scheduling on two unrelated machines

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)