Worst case analysis of greedy type algorithms for independence systems
From MaRDI portal
Publication:3888842
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
combinatorial optimizationapproximative algorithmindependence systemsworst case performancerank quotientgreedy type algorithms
Related Items (15)
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
This page was built for publication: Worst case analysis of greedy type algorithms for independence systems