A trivial algorithm

I seldom talk about my research here. First, there's not much (...); and second, most of them are on very simple (a.k.a. "fundamental") problems. Recently, we have a paper where the "main" result is so simple that some of the reviewers' comments were:

• simple to the point of triviality

• The new algorithm is almost trivial. It can be seen as a "real" result only due to the fact that several researchers tried to design improved algorithms in the past but did not succeed.

(Actually, I plan to put these comments on the slides in the talk.)

So here is the problem. A set of equal-length intervals arrive online. Each interval carries a weight. The objective is to choose a set of non-overlapping intervals in an online manner such that the total weight of the chosen intervals is maximized. An interval can be discarded (preempted) in favour of another newly-arriving interval.

A deterministic 4-competitive algorithm is known and is optimal (Woeginger, TCS, 1994). The question is: give a better randomized algorithm.

Our trivial algorithm is 2-competitive. Since it is so trivial I'll not describe it here but leave it for you to imagine. Either people do not care about the problem (except this, this and this) or people have come up with this many times and didn't bother to write about it...