Online scheduling with interval conflicts

In the problem of Scheduling with Interval Conflicts, there is a ground set of items indexed by integers, and the input is a collection of conflicts, each containing all the items whose index lies within some interval on the real line. Conflicts arrive in an online fashion. A scheduling algorithm must select, from each conflict, at most one survivor item, and the goal is to max-imize the number (or weight) of items that survive all the conflicts they are involved in. We present a centralized deterministic online algorithm whose competitive ratio is O(lg σ), where σ is the size of the largest conflict. For the distributed setting, we present another deterministic algorithm whose competitive ratio is 2 ⌈lg σ ⌉ in the special contiguous case, in which the item indices constitute a contiguous interval of integers. Our upper bounds are complemented by two lower bounds: one that shows that even in the contiguous case, all deterministic algorithms (centralized or distributed) have competitive ratio Ω(lg σ), and that in the non-contiguous case, no deterministic oblivious algorithm (i.e., a distributed algorithm that does not use communi-cation) can have a bounded competitive ratio