论文标题
圆形和圆形sap的近似算法
Approximation Algorithms for ROUND-UFP and ROUND-SAP
论文作者
论文摘要
我们研究了圆形和圆形SAP，这是经典垃圾箱堆积问题的两个概括，这些问题分别对应于路径（UFP）和存储分配问题（SAP）上的不可填充流问题。为我们提供了一条能力的路径，其边缘和一组任务，其中每个任务都会得到需求和一个子路径。在Found-UFP中，目标是将所有任务包装成给定路径的最少副本（圆），以便对于每个副本，任何边缘上任务的总需求都不会超过相应边缘的容量。在圆形sap中，任务被认为是矩形，目标是将这些矩形的非重叠包装填充成最少数量的回合，以使所有矩形完全位于边缘的容量概况以下。 我们表明，与垃圾箱堆积相比，即使所有边缘能力相等，这两个问题也不承认渐近多项式近似方案（APTA）。但是，对于这种设置，我们获得了两个问题的渐近$（2+ \ varepsilon）$ - 近似值。对于一般情况，我们获得了$ O（\ log \ log n）$ - 近似算法和$ o（\ log \ log \ frac {1}δ）$ - 在$（1+Δ）$ - 两个问题的资源增强下的近似值。对于NO瓶颈假设的中间设置（即，最大任务需求最多是最小边缘容量），我们分别获得了圆形UFP和圆形安全性的绝对$ 12 $ - 和渐近$（16+ \ varepsilon）$ - 近似算法。
We study ROUND-UFP and ROUND-SAP, two generalizations of the classical BIN PACKING problem that correspond to the unsplittable flow problem on a path (UFP) and the storage allocation problem (SAP), respectively. We are given a path with capacities on its edges and a set of tasks where for each task we are given a demand and a subpath. In ROUND-UFP, the goal is to find a packing of all tasks into a minimum number of copies (rounds) of the given path such that for each copy, the total demand of tasks on any edge does not exceed the capacity of the respective edge. In ROUND-SAP, the tasks are considered to be rectangles and the goal is to find a non-overlapping packing of these rectangles into a minimum number of rounds such that all rectangles lie completely below the capacity profile of the edges. We show that in contrast to BIN PACKING, both the problems do not admit an asymptotic polynomial-time approximation scheme (APTAS), even when all edge capacities are equal. However, for this setting, we obtain asymptotic $(2+\varepsilon)$-approximations for both problems. For the general case, we obtain an $O(\log\log n)$-approximation algorithm and an $O(\log\log\frac{1}δ)$-approximation under $(1+δ)$-resource augmentation for both problems. For the intermediate setting of the no bottleneck assumption (i.e., the maximum task demand is at most the minimum edge capacity), we obtain absolute $12$- and asymptotic $(16+\varepsilon)$-approximation algorithms for ROUND-UFP and ROUND-SAP, respectively.
