An Analysis of the Greedy Heuristic for Independence Systems
DOI10.1016/S0167-5060(08)70322-4zbMATH Open0392.90058MaRDI QIDQ4174528FDOQ4174528
Authors: Bernhard Korte, Dirk Hausmann
Publication date: 1978
Published in: Algorithmic Aspects of Combinatorics (Search for Journal in Brave)
Permutations, words, matrices (05A05) Extremal problems in graph theory (05C35) Integer programming (90C10) Combinatorial aspects of matroids and geometric lattices (05B35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Applications of graph theory to circuits and networks (94C15)
Cited In (63)
- Unified Greedy Approximability beyond Submodular Maximization
- Approximation ratio of the min-degree greedy algorithm for maximum independent set on interval and chordal graphs
- Stability and recovery for independence systems
- Linear time approximation algorithms for~degree~constrained subgraph problems
- The power of randomness in Bayesian optimal mechanism design
- A Framework for the Secretary Problem on the Intersection of Matroids
- Approximation algorithms for maximum dispersion
- Relaxing the irrevocability requirement for online graph algorithms
- Approximation for maximizing monotone non-decreasing set functions with a greedy method
- Decentralized algorithms for distributed integer programming problems with a coupling cardinality constraint
- On approximate algorithms for combinatorial linear maximization problems
- K-greedy algorithms for independence systems
- Constrained submodular maximization via a nonsymmetric technique
- Algorithms – ESA 2004
- Clumsy packing of dominoes
- General bounds for incremental maximization
- Greedy algorithm and symmetric matroids
- Hardness and approximation of minimum maximal matchings
- Size versus truthfulness in the house allocation problem
- Robust independence systems
- An approximation algorithm for the maximum traveling salesman problem
- Some recent results in the analysis of greedy algorithms for assignment problems
- Analysis of heuristics for finding a maximum weight planar subgraph
- Surrogate optimization for \(p\)-norms
- Unlabelled Partition Systems: Optimization and Complexity
- Matroid representation of clique complexes
- Minimum partition of an independence system into independent sets
- Computing maximum matchings in temporal graphs
- Unified greedy approximability beyond submodular maximization
- Algorithmic aspects of upper edge domination
- Approximation by lexicographically maximal solutions in matching and matroid intersection problems
- An analysis of the greedy algorithm for partially ordered sets
- Hereditary systems and greedy-type algorithms.
- Maximizing traveling salesman problem for special matrices
- The doubly graded matrix cone and Ferrers matrices
- Evolutionary algorithms and matroid optimization problems
- On the geometric structure of independence systems
- Randomized strategies for cardinality robustness in the knapsack problem
- Randomized greedy matching. II
- Lower bounds on the worst-case complexity of some oracle algorithms
- An estimate for the curvature of an order-convex set in the integer lattice and related questions
- A heuristic lagrangean algorithm for the capacitated plant location problem
- Bounding the payment of approximate truthful mechanisms
- Computing knapsack solutions with cardinality robustness
- Matroids on partially ordered sets
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- Modularity and greed in double auctions
- Small maximal matchings in random graphs.
- Approximations for the maximum acyclic subgraph problem
- Matroidal approximations of independence systems
- An approximation algorithm for a general class of multi-parametric optimization problems
- Recent trends in combinatorial optimization
- Saturation number of fullerene graphs
- Greedy matching: guarantees and limitations
- Exact and approximation algorithms for weighted matroid intersection
- Greedy guarantees for non-submodular function maximization under independent system constraint with applications
- Paroid search: Generic local combinatorial optimization
- On a partition LP relaxation for min-cost 2-node connected spanning subgraphs
- Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location
- Buyback problem -- approximate matroid intersection with cancellation costs
- The 2-quasi-greedy algorithm for cardinality constrained matroid bases
- On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
This page was built for publication: An Analysis of the Greedy Heuristic for Independence Systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4174528)