2026-08-06T21:34:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10662 2024-03-06T10:46:24Z ddc:004 open_access

Scheduling to Approximate Minimization Objectives on Identical Machines Moseley, Benjamin Scheduling LP rounding Approximation Algorithms This paper considers scheduling on identical machines. The scheduling objective considered in this paper generalizes most scheduling minimization problems. In the problem, there are n jobs and each job j is associated with a monotonically increasing function g_j. The goal is to design a schedule that minimizes sum_{j in [n]} g_{j}(C_j) where C_j is the completion time of job j in the schedule. An O(1)-approximation is known for the single machine case. On multiple machines, this paper shows that if the scheduler is required to be either non-migratory or non-preemptive then any algorithm has an unbounded approximation ratio. Using preemption and migration, this paper gives a O(log log nP)-approximation on multiple machines, the first result on multiple machines. These results imply the first non-trivial positive results for several special cases of the problem considered, such as throughput minimization and tardiness. Natural linear programs known for the problem have a poor integrality gap. The results are obtained by strengthening a natural linear program for the problem with a set of covering inequalities we call job cover inequalities. This linear program is rounded to an integral solution by building on quasi-uniform sampling and rounding techniques. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Moseley 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.86 urn:nbn:de:0030-drops-106621 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.86 eng https://creativecommons.org/licenses/by/3.0/legalcode