2026-07-24T06:07:34Z https://drops.dagstuhl.de/oai

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

Matroid Coflow Scheduling Im, Sungjin Moseley, Benjamin Pruhs, Kirk Purohit, Manish Coflow Scheduling Concurrent Open Shop Matroid Scheduling We consider the matroid coflow scheduling problem, where each job is comprised of a set of flows and the family of sets that can be scheduled at any time form a matroid. Our main result is a polynomial-time algorithm that yields a 2-approximation for the objective of minimizing the weighted completion time. This result is tight assuming P != NP. As a by-product we also obtain the first (2+epsilon)-approximation algorithm for the preemptive concurrent open shop scheduling problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sungjin Im and Benjamin Moseley and Kirk Pruhs and Manish Purohit 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.145 urn:nbn:de:0030-drops-107213 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.145 eng https://creativecommons.org/licenses/by/3.0/legalcode