Richard J. Lipton - Online Scheduling

Online Scheduling

Richard Lipton with Andrew Tomkins introduced a randomized online interval scheduling algorithm, the 2-size version being strongly competitive, and the k-size version achieving O(log), as well as demonstrating a theoretical lower-bound of O(log). This algorithm uses a private-coin for randomization and a "virtual" choice to fool a medium adversary.

Being presented with an event the user must decide whether or not to include the event in the schedule. The 2-size virtual algorithm is described by how it reacts to 1-interval or k-intervals being presented by the adversary:

• For a 1-interval, flip a fair coin

  • Heads

    Take the interval

    Tails

    "Virtually" take the interval, but do no work. Take no short interval for the next 1 unit of time.

• For a k-interval, take whenever possible.

Again, this 2-size algorithm is shown to be strongly-competitive. The generalized k-size algorithm which is similar to the 2-size algorithm is then shown to be O(log)-competitive.