1 Search Results for "Kraska, Artur"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.28
Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times

Authors: Marcin Bienkowski, Artur Kraska, and Hsiang-Hsuan Liu

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We present a unified framework for minimizing average completion time for many seemingly disparate online scheduling problems, such as the traveling repairperson problems (TRP), dial-a-ride problems (DARP), and scheduling on unrelated machines. We construct a simple algorithm that handles all these scheduling problems, by computing and later executing auxiliary schedules, each optimizing a certain function on already seen prefix of the input. The optimized function resembles a prize-collecting variant of the original scheduling problem. By a careful analysis of the interplay between these auxiliary schedules, and later employing the resulting inequalities in a factor-revealing linear program, we obtain improved bounds on the competitive ratio for all these scheduling problems. In particular, our techniques yield a 4-competitive deterministic algorithm for all previously studied variants of online TRP and DARP, and a 3-competitive one for the scheduling on unrelated machines (also with precedence constraints). This improves over currently best ratios for these problems that are 5.14 and 4, respectively. We also show how to use randomization to further reduce the competitive ratios to 1+2/ln 3 < 2.821 and 1+1/ln 2 < 2.443, respectively. The randomized bounds also substantially improve the current state of the art. Our upper bound for DARP contradicts the lower bound of 3 given by Fink et al. (Inf. Process. Lett. 2009); we pinpoint a flaw in their proof.
Cite as

Marcin Bienkowski, Artur Kraska, and Hsiang-Hsuan Liu. Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bienkowski_et_al:LIPIcs.ICALP.2021.28,
  author =	{Bienkowski, Marcin and Kraska, Artur and Liu, Hsiang-Hsuan},
  title =	{{Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.28},
  URN =		{urn:nbn:de:0030-drops-140977},
  doi =		{10.4230/LIPIcs.ICALP.2021.28},
  annote =	{Keywords: traveling repairperson problem, dial-a-ride, machine scheduling, unrelated machines, minimizing completion time, competitive analysis, factor-revealing LP}
}
  • Refine by Author
  • 1 Bienkowski, Marcin
  • 1 Kraska, Artur
  • 1 Liu, Hsiang-Hsuan

  • Refine by Classification
  • 1 Theory of computation → Online algorithms
  • 1 Theory of computation → Scheduling algorithms

  • Refine by Keyword
  • 1 competitive analysis
  • 1 dial-a-ride
  • 1 factor-revealing LP
  • 1 machine scheduling
  • 1 minimizing completion time
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact