University of Twente Research Information · 1989 · 155 citations · 0 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsOptimizationAlgorithm AnalysisApproximation AlgorithmsCombinatorial OptimizationData PartitioningGreedy AlgorithmsMatroid TheoryGraph PartitioningGreedy ApproximationGreedy HeuristicsLower BoundsPartition Performance AnalysisPartitioning AlgorithmsPartitioning ProblemsSet Partitioning Problem
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.