@inproceedings{0101371dedc0481eb77fd93eea80ea55,
title = "Bag-of-tasks scheduling on related machines",
abstract = "We consider online scheduling to minimize weighted completion time on related machines, where each job consists of several tasks that can be concurrently executed. A job gets completed when all its component tasks finish. We obtain an O(K3 log2 K)-competitive algorithm in the non-clairvoyant setting, where K denotes the number of distinct machine speeds. The analysis is based on dual-fitting on a precedence-constrained LP relaxation that may be of independent interest.",
keywords = "Approximation algorithms, Bag-of-tasks, Related machines, Scheduling",
author = "Anupam Gupta and Amit Kumar and Sahil Singla",
note = "Publisher Copyright: {\textcopyright} Anupam Gupta, Amit Kumar, and Sahil Singla; licensed under Creative Commons License CC-BY 4.0; 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021 ; Conference date: 16-08-2021 Through 18-08-2021",
year = "2021",
month = sep,
day = "1",
doi = "10.4230/LIPIcs-APPROX/RANDOM.2021.3",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Mary Wootters and Laura Sanita",
booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021",
}