Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems |
| |
| Authors: | A Warburton |
| |
| Institution: | (1) Faculty of Administration, University of Ottawa, Canada |
| |
| Abstract: | Min-max problems on matroids are NP-hard for a wide variety of matroids. However, greedy type algorithms have data independent worst case performance guarantees, andn-enumerative algorithms yield -optimal solutions ifn is sufficiently close to the rank of the underlying matroid. Data dependent performance guarantees can be obtained for max-min problems over matroids.This research was partially supported by NSERC Grant A5543. |
| |
| Keywords: | Matroids Combinatorial Optimization Heuristics Greedy Algorithms Min-Max Problems Enumerative Heuristics |
| 本文献已被 SpringerLink 等数据库收录！ |
