Anti-matroids

DOI10.1016/S0167-6377(02)00117-7MaRDI QIDQ1612010zbMATH OpenOpenAlexFDO

Authors G. Gutin, A. Yeo

Publication date 28 August 2002

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0167-6377(02)00117-7

zbMATH Keywords

anti-matroidscombinatorial optimizationgreedy algorithmtraveling Salesman problem

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Combinatorial optimization (90C27)

Recommendations

• An algorithmic characterization of antimatroids
• Greedoids
• scientific article; zbMATH DE number 4191655
• Antimatroids induced by matchings
• Greedy algorithm and symmetric matroids

Cites work

• Domination analysis of some heuristics for the traveling salesman problem
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 3543841 (Why is no real title available?)
• Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
• Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
• TSP heuristics: domination analysis and complexity
• TSP tour domination and Hamilton cycle decompositions of regular digraphs

Cited in

(7)

• A single-element extension of antimatroids
• When the greedy algorithm fails
• Antimatroids and balanced pairs
• An algorithmic characterization of antimatroids
• Two Characterizations of Antimatroids
• Domination analysis for minimum multiprocessor scheduling
• Greedy-type resistance of combinatorial problems

This page was built for publication: Anti-matroids

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