License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.36
URN: urn:nbn:de:0030-drops-171581
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17158/
Go to the corresponding LIPIcs Volume Portal

Fukunaga, Takuro

Integrality Gap of Time-Indexed Linear Programming Relaxation for Coflow Scheduling

pdf-format:
LIPIcs-APPROX36.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{fukunaga:LIPIcs.APPROX/RANDOM.2022.36,
  author =	{Fukunaga, Takuro},
  title =	{{Integrality Gap of Time-Indexed Linear Programming Relaxation for Coflow Scheduling}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{36:1--36:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17158},
  URN =		{urn:nbn:de:0030-drops-171581},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.36},
  annote =	{Keywords: coflow scheduling, hypergraph matching, approximation algorithm}
}

Keywords: coflow scheduling, hypergraph matching, approximation algorithm
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Issue Date: 2022
Date of publication: 15.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI