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

(62)

Approximation ratio of the min-degree greedy algorithm for maximum independent set on interval and chordal graphs
Unified Greedy Approximability beyond Submodular Maximization
Stability and recovery for independence systems
Matroidal approximations of independence systems
The 2-quasi-greedy algorithm for cardinality constrained matroid bases
On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location
On the geometric structure of independence systems
Robust independence systems
Algorithms – ESA 2004
Paroid search: Generic local combinatorial optimization
Matroids on partially ordered sets
A heuristic lagrangean algorithm for the capacitated plant location problem
Bounding the payment of approximate truthful mechanisms
On approximate algorithms for combinatorial linear maximization problems
General bounds for incremental maximization
Algorithmic aspects of upper edge domination
Surrogate optimization for \(p\)-norms
On the algorithmic complexity of twelve covering and independence parameters of graphs
Buyback problem -- approximate matroid intersection with cancellation costs
Approximation by lexicographically maximal solutions in matching and matroid intersection problems
Hardness and approximation of minimum maximal matchings
Lower bounds on the worst-case complexity of some oracle algorithms
The power of randomness in Bayesian optimal mechanism design
On a partition LP relaxation for min-cost 2-node connected spanning subgraphs
Small maximal matchings in random graphs.
Unlabelled Partition Systems: Optimization and Complexity
An approximation algorithm for a general class of multi-parametric optimization problems
A Framework for the Secretary Problem on the Intersection of Matroids
Greedy algorithm and symmetric matroids
Hereditary systems and greedy-type algorithms.
K-greedy algorithms for independence systems
Size versus truthfulness in the house allocation problem
Computing knapsack solutions with cardinality robustness
Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
Some recent results in the analysis of greedy algorithms for assignment problems
Approximation algorithms for maximum dispersion
Constrained submodular maximization via a nonsymmetric technique
Randomized strategies for cardinality robustness in the knapsack problem
Linear time approximation algorithms for~degree~constrained subgraph problems
An analysis of the greedy algorithm for partially ordered sets
Exact and approximation algorithms for weighted matroid intersection
Greedy guarantees for non-submodular function maximization under independent system constraint with applications
Randomized greedy matching. II
Approximations for the maximum acyclic subgraph problem
Modularity and greed in double auctions
Recent trends in combinatorial optimization
Approximation for maximizing monotone non-decreasing set functions with a greedy method
Minimum partition of an independence system into independent sets
Saturation number of fullerene graphs
Evolutionary algorithms and matroid optimization problems
Matroid representation of clique complexes
Greedy matching: guarantees and limitations
An approximation algorithm for the maximum traveling salesman problem
Decentralized algorithms for distributed integer programming problems with a coupling cardinality constraint
The doubly graded matrix cone and Ferrers matrices
An estimate for the curvature of an order-convex set in the integer lattice and related questions
Clumsy packing of dominoes
Maximizing traveling salesman problem for special matrices
Computing maximum matchings in temporal graphs
Analysis of heuristics for finding a maximum weight planar subgraph
Unified greedy approximability beyond submodular maximization

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)