An Analysis of the Greedy Heuristic for Independence Systems
From MaRDI portal
Publication:4174528
DOI10.1016/S0167-5060(08)70322-4zbMath0392.90058MaRDI QIDQ4174528
Publication date: 1978
Published in: Algorithmic Aspects of Combinatorics (Search for Journal in Brave)
05C35: Extremal problems in graph theory
90C10: Integer programming
05A05: Permutations, words, matrices
90C08: Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
05B35: Combinatorial aspects of matroids and geometric lattices
94C15: Applications of graph theory to circuits and networks
Related Items
Randomized greedy matching. II, Algorithms – ESA 2004, Recent trends in combinatorial optimization, Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem, A heuristic lagrangean algorithm for the capacitated plant location problem, Evolutionary algorithms and matroid optimization problems, Saturation number of fullerene graphs, Minimum partition of an independence system into independent sets, Analysis of heuristics for finding a maximum weight planar subgraph, The 2-quasi-greedy algorithm for cardinality constrained matroid bases, Clumsy packing of dominoes, An analysis of the greedy algorithm for partially ordered sets, Lower bounds on the worst-case complexity of some oracle algorithms, Matroids on partially ordered sets, On the algorithmic complexity of twelve covering and independence parameters of graphs, Some recent results in the analysis of greedy algorithms for assignment problems, Approximations for the maximum acyclic subgraph problem, Maximizing traveling salesman problem for special matrices, Approximation algorithms for maximum dispersion, The doubly graded matrix cone and Ferrers matrices, Small maximal matchings in random graphs., Hereditary systems and greedy-type algorithms., Paroid search: Generic local combinatorial optimization, On the geometric structure of independence systems, Matroid representation of clique complexes, Unlabelled Partition Systems: Optimization and Complexity, Greedy algorithm and symmetric matroids, On approximate algorithms for combinatorial linear maximization problems, On the worst-case performance of some algorithms for the asymmetric traveling salesman problem, K-greedy algorithms for independence systems
