An Analysis of the Greedy Heuristic for Independence Systems

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)