An Analysis of the Greedy Heuristic for Independence Systems

Permutations, words, matrices (05A05) Combinatorial aspects of matroids and geometric lattices (05B35) Extremal problems in graph theory (05C35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Integer programming (90C10) Applications of graph theory to circuits and networks (94C15)

Cited in

(67)

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.
Randomized strategies for cardinality robustness in the knapsack problem
Paroid search: Generic local combinatorial optimization
On the geometric structure of independence systems
Computing knapsack solutions with cardinality robustness
Surrogate optimization for \(p\)-norms
Algorithmic aspects of upper edge domination
An approximation algorithm for a general class of multi-parametric optimization problems
General bounds for incremental maximization
Approximation by lexicographically maximal solutions in matching and matroid intersection problems
Decentralized algorithms for distributed integer programming problems with a coupling cardinality constraint
Exact and approximation algorithms for weighted matroid intersection
Size versus truthfulness in the house allocation problem
The power of randomness in Bayesian optimal mechanism design
Matroid representation of clique complexes
Modularity and greed in double auctions
Matroidal approximations of independence systems
Greedy guarantees for non-submodular function maximization under independent system constraint with applications
An approximation algorithm for the maximum traveling salesman problem
Hardness and approximation of minimum maximal matchings
Linear time approximation algorithms for~degree~constrained subgraph problems
Buyback problem -- approximate matroid intersection with cancellation costs
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
Randomized greedy matching. II
Bounding the payment of approximate truthful mechanisms
A Framework for the Secretary Problem on the Intersection of Matroids
Constrained submodular maximization via a nonsymmetric technique
Stability and recovery for independence systems
Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location
Greedy matching: guarantees and limitations
Algorithms – ESA 2004
Robust independence systems
Approximation for maximizing monotone non-decreasing set functions with a greedy method
On a partition LP relaxation for min-cost 2-node connected spanning subgraphs
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
Approximation ratio of the min-degree greedy algorithm for maximum independent set on interval and chordal graphs
Submodular maximization subject to matroid intersection on the fly
Maximizing minimum cycle bases intersection
On inner independence systems
Semi-streaming algorithms for hypergraph matching
A formal analysis of algorithms for matroids and greedoids
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

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)