首页> 外文期刊>Algorithmica >Variable Sized Online Interval Coloring with Bandwidth
【24h】

Variable Sized Online Interval Coloring with Bandwidth

机译:具有带宽的可变大小的在线间隔着色

获取原文
获取原文并翻译 | 示例

摘要

We consider online coloring of intervals with bandwidth in a setting where colors have variable capacities. Whenever the algorithm opens a new color, it must choose the capacity for that color and cannot change it later. A set of intervals can be assigned the same color a of capacity C_a if the sum of bandwidths of intervals at each point does not exceed C_a. The goal is to minimize the total capacity of all the colors used. We consider the bounded model, where all capacities must be chosen in the range (0, 1), and the unbounded model, where the algorithm may use colors of any positive capacity. For the absolute competitive ratio, we give an upper bound of 14 and a lower bound of 4.59 for the bounded model, and an upper bound of 4 and a matching lower bound of 4 for the unbounded model. We also consider the offline version of these problems and show that whereas the unbounded model is polynomially solvable, the bounded model is NP-hard in the strong sense and admits a 3.6-approximation algorithm.
机译:我们考虑在颜色具有可变容量的情况下,对具有带宽的间隔进行在线着色。每当算法打开新颜色时,它都必须选择该颜色的容量,并且以后不能更改。如果每个点处的间隔带宽之和不超过C_a,则可以为一组间隔分配相同的颜色,容量为C_a。目标是使所有使用的颜色的总容量最小化。我们考虑有界模型和无界模型,在有界模型中必须在(0,1)范围内选择所有容量,在无界模型中算法可以使用任何正容量的颜色。对于绝对竞争比率,对于有界模型,给定上限为14,下界为4.59,对于无​​界模型,给定上限为4,匹配的下界为4。我们还考虑了这些问题的脱机版本,并表明尽管无界模型是多项式可解的,但有界模型在很强的意义上是NP-hard的,并且接受3.6近似算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号