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)
Extremal problems in graph theory (05C35) Integer programming (90C10) Permutations, words, matrices (05A05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial aspects of matroids and geometric lattices (05B35) Applications of graph theory to circuits and networks (94C15)
Related Items
The 2-quasi-greedy algorithm for cardinality constrained matroid bases, Approximations for the maximum acyclic subgraph problem, An approximation algorithm for the maximum traveling salesman problem, Maximizing traveling salesman problem for special matrices, Evolutionary algorithms and matroid optimization problems, Matroid representation of clique complexes, Clumsy packing of dominoes, Approximation algorithms for maximum dispersion, Hardness and approximation of minimum maximal matchings, Matroidal approximations of independence systems, A Framework for the Secretary Problem on the Intersection of Matroids, Randomized strategies for cardinality robustness in the knapsack problem, Modularity and greed in double auctions, Computing knapsack solutions with cardinality robustness, The doubly graded matrix cone and Ferrers matrices, Randomized greedy matching. II, On a partition LP relaxation for min-cost 2-node connected spanning subgraphs, Constrained Submodular Maximization via a Nonsymmetric Technique, Greedy algorithm and symmetric matroids, Small maximal matchings in random graphs., Unified Greedy Approximability beyond Submodular Maximization, Unified greedy approximability beyond submodular maximization, Computing maximum matchings in temporal graphs, An estimate for the curvature of an order-convex set in the integer lattice and related questions, Greedy guarantees for non-submodular function maximization under independent system constraint with applications, Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems, Hereditary systems and greedy-type algorithms., An analysis of the greedy algorithm for partially ordered sets, Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location, Decentralized algorithms for distributed integer programming problems with a coupling cardinality constraint, Bounding the payment of approximate truthful mechanisms, Saturation number of fullerene graphs, Buyback Problem - Approximate Matroid Intersection with Cancellation Costs, Greedy matching: guarantees and limitations, Surrogate optimization for \(p\)-norms, Unlabelled Partition Systems: Optimization and Complexity, Algorithmic aspects of upper edge domination, Approximation for maximizing monotone non-decreasing set functions with a greedy method, Lower bounds on the worst-case complexity of some oracle algorithms, K-greedy algorithms for independence systems, Robust Independence Systems, Paroid search: Generic local combinatorial optimization, Relaxing the irrevocability requirement for online graph algorithms, Algorithms – ESA 2004, Minimum partition of an independence system into independent sets, Matroids on partially ordered sets, On approximate algorithms for combinatorial linear maximization problems, Exact and approximation algorithms for weighted matroid intersection, On the geometric structure of independence systems, Size versus truthfulness in the house allocation problem, On the algorithmic complexity of twelve covering and independence parameters of graphs, An approximation algorithm for a general class of multi-parametric optimization problems, Stability and Recovery for Independence Systems, 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, On the worst-case performance of some algorithms for the asymmetric traveling salesman problem, A heuristic lagrangean algorithm for the capacitated plant location problem, Analysis of heuristics for finding a maximum weight planar subgraph, The power of randomness in Bayesian optimal mechanism design, Some recent results in the analysis of greedy algorithms for assignment problems, General bounds for incremental maximization, Approximation by lexicographically maximal solutions in matching and matroid intersection problems
