On the performance of on-line algorithms for partition problems
Ulrich Faigle, Walter Kern, G. Turán · University of Twente Research Information · 1989
We consider the performance of the greedy algorithm and of on-line algorithms for partition problems in combinatorial optimization. After surveying known resuls we give bounds for matroid and graph partitioning, and discuss the power of non-adaptive adversaries for proving lower bounds.