Worst case analysis of greedy type algorithms for independence systems

DOI10.1007/BFb0120891zbMath0444.90070OpenAlexW60525624MaRDI QIDQ3888842

Bernhard Korte, Dirk Hausmann, T. A. Jenkyns

Publication date: 1980

Published in: Mathematical Programming Studies (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bfb0120891

zbMATH Keywords

combinatorial optimizationapproximative algorithmindependence systemsworst case performancerank quotientgreedy type algorithms

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10)

Related Items

Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems, Homotopy base of acyclic graphs - a combinatorial analysis of commutative diagrams by means of preordered matroid, Two-way greedy: algorithms for imperfect rationality, Matroidal approximations of independence systems, Constrained Submodular Maximization via a Nonsymmetric Technique, A new greedy algorithm for the quadratic assignment problem, Submodular optimization problems and greedy strategies: a survey, An analysis of the greedy algorithm for partially ordered sets, Paroids: A canonical format for combinatorial optimization, Performance bounds with curvature for batched greedy optimization, Paroid search: Generic local combinatorial optimization, Minimum partition of an independence system into independent sets, Robust Randomized Matchings, Heuristic methods and applications: A categorized survey, Informative path planning as a maximum traveling salesman problem with submodular rewards