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

DOI10.1007/BF01582247zbMath0581.90062OpenAlexW2014999649MaRDI QIDQ3703589

No author found.

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)

Related Items (7)

A decision-theoretic approach to robust optimization in multivalued graphs ⋮ A note on \(K\) best network flows ⋮ Minmax combinatorial optimization ⋮ Exact algorithms for OWA-optimization in multiobjective spanning tree problems ⋮ On matroids with multiple objectives ⋮ Note on combinatorial optimization with max-linear objective functions ⋮ Heuristic methods and applications: A categorized survey

Cites Work

• Unnamed Item
• Worst case analysis of greedy type algorithms for independence systems
• Algorithms for Scheduling Independent Tasks
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Approximate Algorithms for the 0/1 Knapsack Problem
• An analysis of approximations for maximizing submodular set functions—I
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

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