License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.86
URN: urn:nbn:de:0030-drops-181386
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18138/
Go to the corresponding LIPIcs Volume Portal

Li, Shi

Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems

pdf-format:
LIPIcs-ICALP-2023-86.pdf (1.0 MB)

Abstract

We study nearly-linear time approximation algorithms for non-preemptive scheduling problems in two settings: the unrelated machine setting, and the identical machine with job precedence constraints setting, under the well-studied objectives such as makespan and weighted completion time. For many problems, we develop nearly-linear time approximation algorithms with approximation ratios matching the current best ones achieved in polynomial time.
Our main technique is linear programming relaxation. For the unrelated machine setting, we formulate mixed packing and covering LP relaxations of nearly-linear size, and solve them approximately using the nearly-linear time solver of Young. For the makespan objective, we develop a rounding algorithm with (2+ε)-approximation ratio. For the weighted completion time objective, we prove the LP is as strong as the rectangle LP used by Im and Li, leading to a nearly-linear time (1.45 + ε)-approximation for the problem.
For problems in the identical machine with precedence constraints setting, the precedence constraints can not be formulated as packing or covering constraints. To achieve the nearly-linear running time, we define a polytope for the constraints, and leverage the multiplicative weight update (MWU) method with an oracle which always returns solutions in the polytope.

BibTeX - Entry

@InProceedings{li:LIPIcs.ICALP.2023.86,
  author =	{Li, Shi},
  title =	{{Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{86:1--86:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18138},
  URN =		{urn:nbn:de:0030-drops-181386},
  doi =		{10.4230/LIPIcs.ICALP.2023.86},
  annote =	{Keywords: Nearly-Linear Time, Sheduling, Approximation Algorithms}
}

Keywords: Nearly-Linear Time, Sheduling, Approximation Algorithms
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI