Randomized online interval scheduling

Online interval scheduling problems arise in important application areas such as continuous media and call control. Woeginger gives an optimal 4-competitive deterministic algorithm for online interval scheduling. He leaves as an open problem whether randomization can be used to achieve a competitive ratio less than 4. A randomized (2 + √(3) < 3.73206)-competitive algorithm is presented for the case where a job of length l has value φ(l), where φ() is any continuous convex non-negative function with φ(0) = 0.