We propose two strategies for Presenter in the on-line interval graph coloring games. Specifically, we consider a setting in which each interval is associated with a d-dimensional vector of weights and the coloring needs to satisfy the d-dimensional bandwidth constraint, and the k-cardinality constraint. Such a variant was first introduced by Epstein and Levy and it is a natural model for resource-aware task scheduling with d different shared resources where at most k tasks can be scheduled simultaneously on a single machine. The first strategy forces any on-line interval coloring algorithm to use at least (5m - 3) d/log d+3 different colors on an m(d/k + log d + 3)-colorable set of intervals. The second strategy forces any on-line interval coloring algorithm to use at least [5m/2]d/ log d+3 different colors on an m(d/k + log d + 3)-colorable set of unit intervals.
展开▼
机译：我们为在线间隔图着色游戏中的Presenter提出了两种策略。具体地，我们考虑一种设置，其中每个间隔与权重的d维向量相关联，并且着色需要满足d维带宽约束和k基数约束。这种变体由Epstein和Levy首次提出，它是具有d种不同共享资源的资源感知任务调度的自然模型，其中最多k个任务可以在一台机器上同时进行调度。第一种策略强制任何在线间隔着色算法在m（d / k + log d + 3）个可着色间隔上使用至少（5m-3）d / log d + 3种不同的颜色。第二种策略强制任何在线间隔着色算法在m（d / k + log d + 3）可着色的单位间隔集上至少使用[5m / 2] d / log d + 3种不同的颜色。
展开▼
