Lower Bounds for On line Interval Coloring with Vector and Cardinality Constraints
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.
SOFSEM