Improved bounds for scheduling conflicting jobs with minsum criteria

DOI10.1145/1328911.1328922zbMath1446.90078OpenAlexW2139534004MaRDI QIDQ4962703

Magnús M. Halldórsson, Rajiv Gandhi, Hadas Shachnai, Guy Kortsarz

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1328911.1328922

zbMATH Keywords

linear programmingschedulingcoloringapproximation algorithmsLP-roundingsum multicoloring

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (9)

On the performance guarantee of first fit for sum coloring ⋮ Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints ⋮ Improved bounds for randomized preemptive online matching ⋮ Non-clairvoyant scheduling with conflicts for unit-size jobs ⋮ On a local protocol for concurrent file transfers ⋮ Scheduling Problems over Network of Machines ⋮ Scheduling problems over a network of machines ⋮ On sum coloring and sum multi-coloring for restricted families of graphs ⋮ A polynomial-time approximation scheme for the airplane refueling problem

This page was built for publication: Improved bounds for scheduling conflicting jobs with minsum criteria