Before revision:  It has been open ever since whether there is an algorithm for general bids better than the 0.5-competitive greedy algorithm.
After revision:  It has been open ever since whether there is an algorithm for general bids better than the 0.5-competitive greedy algorithm.