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

Integrality Gap of Time-Indexed Linear Programming Relaxation for Coflow Scheduling
复制标题

DOI：
10.4230/lipics.approx/random.2022.36
复制
发表时间：
2022
期刊：
--
影响因子：
--
通讯作者：
Takuro Fukunaga
Takuro Fukunaga
中科院分区：
其他
文献类型：
--
作者：
Takuro Fukunaga

文献摘要

相似文献

Coflow是网络中一组相关的并行数据流。协流调度的目标是处理给定协流的所有需求，同时最小化加权完成时间。众所周知，协流调度问题允许多种多项式时间 5 近似算法通过舍入问题的线性规划 (LP) 松弛来计算解决方案。在本文中，我们研究了协流调度的时间索引 LP 松弛。我们证明了时间索引 LP 松弛的完整性差距最多为 4。我们还证明了另一种多项式时间 5 近似算法可以通过对时间索引 LP 松弛的解进行舍入来获得。
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.