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)

Linear time approximation algorithms for~degree~constrained subgraph problems
The power of randomness in Bayesian optimal mechanism design
Approximation algorithms for maximum dispersion
Decentralized algorithms for distributed integer programming problems with a coupling cardinality constraint
A Framework for the Secretary Problem on the Intersection of Matroids
Approximation for maximizing monotone non-decreasing set functions with a greedy method
On approximate algorithms for combinatorial linear maximization problems
K-greedy algorithms for independence systems
Unified Greedy Approximability beyond Submodular Maximization
Constrained submodular maximization via a nonsymmetric technique
Clumsy packing of dominoes
Algorithms – ESA 2004
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
An approximation algorithm for the maximum traveling salesman problem
Robust independence systems
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
Algorithmic aspects of upper edge domination
Computing maximum matchings in temporal graphs
Unified greedy approximability beyond submodular maximization
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
Lower bounds on the worst-case complexity of some oracle algorithms
Randomized greedy matching. II
An estimate for the curvature of an order-convex set in the integer lattice and related questions
Bounding the payment of approximate truthful mechanisms
A heuristic lagrangean algorithm for the capacitated plant location problem
Computing knapsack solutions with cardinality robustness
Matroids on partially ordered sets
On the algorithmic complexity of twelve covering and independence parameters of graphs
Approximation ratio of the min-degree greedy algorithm for maximum independent set on interval and chordal graphs
Modularity and greed in double auctions
Small maximal matchings in random graphs.
Stability and recovery for independence systems
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
Greedy matching: guarantees and limitations
Saturation number of fullerene graphs
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
Buyback problem -- approximate matroid intersection with cancellation costs
Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location
The 2-quasi-greedy algorithm for cardinality constrained matroid bases
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

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)