2026-08-07T03:51:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17158 2024-03-06T10:59:07Z ddc:004 open_access

Integrality Gap of Time-Indexed Linear Programming Relaxation for Coflow Scheduling Fukunaga, Takuro coflow scheduling hypergraph matching approximation algorithm Coflow is a set of related parallel data flows in a network. The goal of the coflow scheduling is to process all the demands of the given coflows while minimizing the weighted completion time. It is known that the coflow scheduling problem admits several polynomial-time 5-approximation algorithms that compute solutions by rounding linear programming (LP) relaxations of the problem. In this paper, we investigate the time-indexed LP relaxation for coflow scheduling. We show that the integrality gap of the time-indexed LP relaxation is at most 4. We also show that yet another polynomial-time 5-approximation algorithm can be obtained by rounding the solutions to the time-indexed LP relaxation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Takuro Fukunaga 2022 Is Part Of LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2022.36 urn:nbn:de:0030-drops-171581 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.36 eng https://creativecommons.org/licenses/by/4.0/legalcode