文章基本信息

标题：Matroid Coflow Scheduling
本地全文：下载
作者：Sungjin Im ; Benjamin Moseley ; Kirk Pruhs 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：132
页码：1-13
DOI：10.4230/LIPIcs.ICALP.2019.145
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Coflow Scheduling; Concurrent Open Shop; Matroid Scheduling