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(logformula_1), as well as demonstrating a theoretical lower-bound of o(logformula_2). this algorithm uses a private-coin for randomization and a "virtual" choice to fool a medium adversary.