Greedy-type resistance of combinatorial problems

DOI10.1016/J.DISOPT.2006.03.001MaRDI QIDQ865746zbMATH OpenOpenAlexFDO

Authors Gareth Bendall, François Margot

Publication date 20 February 2007

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2006.03.001

zbMATH Keywords

greedy algorithmsdomination analysisgreedy resistance

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• Some results on greedy algorithm conjectures
• Greedy algorithms and poset matroids
• Greedy sets and related problems
• Greedy algorithm compatibility and heavy-set structures
• The complexity of the matroid-greedoid partition problem
• Problems on independence systems solvable by the greedy algorithm
• The greedy algorithm and Coxeter matroids
• scientific article; zbMATH DE number 1875441
• scientific article; zbMATH DE number 2044949
• Greedy in Approximation Algorithms

Cites work

• scientific article; zbMATH DE number 3898613 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 5047784 (Why is no real title available?)
• Anti-matroids
• Combinatorial optimization. Theory and algorithms.
• Domination analysis of combinatorial optimization problems.
• TSP heuristics: domination analysis and complexity
• The traveling salesman problem and its variations
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
• When the greedy algorithm fails

Cited in

(2)

• A scheduling problem in the baking industry
• Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems

This page was built for publication: Greedy-type resistance of combinatorial problems

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