Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems

DOI10.1007/BF01582247MaRDI QIDQ3703589zbMATH OpenOpenAlexFDO

Authors

Publication date 1985

Published in Mathematical Programming (Search for Journal in Brave)

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

zbMATH Keywords

heuristicscombinatorial optimizationworst case analysis\(\epsilon \) -optimal solutionsgreedy type algorithmsMin-max problems on matroidsn-enumerative algorithms

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• Hereditary systems and greedy-type algorithms.
• scientific article; zbMATH DE number 194516
• Performance guarantees for greedy algorithms for problems on hereditary systems
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Algorithms for Scheduling Independent Tasks
• An analysis of approximations for maximizing submodular set functions—I
• Approximate Algorithms for the 0/1 Knapsack Problem
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Worst case analysis of greedy type algorithms for independence systems

Cited in

(10)

• Performance guarantees for greedy algorithms for problems on hereditary systems
• On matroids with multiple objectives
• Heuristic methods and applications: A categorized survey
• Note on combinatorial optimization with max-linear objective functions
• Worst case analysis of two heuristics for the set partitioning problem
• Exact algorithms for OWA-optimization in multiobjective spanning tree problems
• A decision-theoretic approach to robust optimization in multivalued graphs
• Minmax combinatorial optimization
• A note on \(K\) best network flows
• Worst Case Analysis of Max-Regret, Greedy and Other Heuristics for Multidimensional Assignment and Traveling Salesman Problems

This page was built for publication: Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3703589)