Improved Bounds for Scheduling Flows under Endpoint Capacity Constraints
Improved Bounds for Scheduling Flows under Endpoint Capacity Constraints
复制标题
DOI：
10.1137/1.9781611977059.1
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Searidang Pa;R. Rajaraman;David Stalfa
中科院分区：
文献类型：
--
作者：
Searidang Pa;R. Rajaraman;David Stalfa
研究了节点容量约束下的流调度问题。我们被赋予能力限制节点和一个在线作业序列，每个作业都有一个释放时间和一个在两个节点之间路由的需求。调度指定了每个步骤中路由哪些作业，保证任何步骤中节点上的总需求最多是其容量。此场景中的一个关键度量是响应时间：作业发布和完成之间的时间。先前的工作表明，没有未增强的算法在平均响应时间上具有竞争力，并且在增强超过2的情况下可以实现恒定的因子竞争比（Dinitz-Moseley Infocom 2020）。对于最大响应时间，最知名的结果是具有增强4的2-竞争算法（Jahanjou et al SPAA 2020）。我们在各种响应时间目标下改进了这些界限。我们表明，没有资源增加，最大响应时间的最佳竞争比是$\Omega（n）$，其中$n$是节点的数量。我们的比例分配算法使用$（1+\vareprogram）$资源增加，以实现$（1/\vareprogram）$-竞争比的设置与一般的需求和能力，可拆分的工作。我们的批量分解算法是2美元竞争力（分别为，最佳的）用于使用资源增加2的最大响应时间（分别地，4)在单位需求和能力，以及不可分割的工作设置。我们还推导出的平均和最大响应时间指标的同时近似的界限。
We study flow scheduling under node capacity constraints. We are given capacitated nodes and an online sequence of jobs, each with a release time and a demand to be routed between two nodes. A schedule specifies which jobs are routed in each step, guaranteeing that the total demand on a node in any step is at most its capacity. A key metric in this scenario is response time: the time between a job's release and its completion. Prior work shows no un-augmented algorithm is competitive for average response time, and that a constant factor competitive ratio is achievable with augmentation exceeding 2 (Dinitz-Moseley Infocom 2020). For maximum response time, the best known result is a 2-competitive algorithm with a augmentation 4 (Jahanjou et al SPAA 2020). We improve these bounds under various response time objectives. We show that, without resource augmentation, the best competitive ratio for maximum response time is $\Omega(n)$, where $n$ is the number of nodes. Our Proportional Allocation algorithm uses $(1+\varepsilon)$ resource augmentation to achieve a $(1/\varepsilon)$-competitive ratio in the setting with general demands and capacities, and splittable jobs. Our Batch Decomposition algorithm is $2$-competitive (resp., optimal) for maximum response time using resource augmentation 2 (resp., 4) in the setting with unit demands and capacities, and unsplittable jobs. We also derive bounds for the simultaneous approximation of average and maximum response time metrics.