Matroids and the greedy algorithm

Cites work

Maximum matching and a polyhedron with 0,1-vertices
Note on Independence Functions
On the Abstract Properties of Linear Dependence
On the shortest spanning subtree of a graph and the traveling salesman problem
Optimum branchings
Systems of distinct representatives and linear algebra

Cited in

(only showing first 100 items - show all)

A new algorithm for the intersection of a line with the independent set polytope of a matroid
A general model for matroids and the greedy algorithm
The \(S\)-digraph optimization problem and the greedy algorithm
Priority algorithms for graph optimization problems
An algorithm for finding a matroid basis which maximizes the product of the weights of the elements
The 2-quasi-greedy algorithm for cardinality constrained matroid bases
The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm
A Mazur-Orlicz type theorem for submodular set functions
A greedy algorithm for hereditary set systems and a generalization of the Rado-Edmonds characterization of matroids
Generalized polymatroids and submodular flows
Polyhedra of regular p-nary group problems
Forest covers and a polyhedral intersection theorem
A generalization of antiwebs to independence systems and their canonical facets
On the spanning tree polyhedron
Subspaces with well-scaled frames
The greedy algorithm for partially ordered sets
A combinatorial optimization problem: optimal generalized cycle bases
A comparative study of heuristics for a two-level routing-location problem
Discrete extremal problems
On the budget-restricted max flow problem
An analysis of the greedy algorithm for partially ordered sets
The image of weighted combinatorial problems
On the diameter of convex polytopes
An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem
Analysis of the Held-Karp lower bound for the asymmetric TSP
Two algorithms for matroids
A combinatorial ranking problem
An unbounded matroid intersection polyhedron
Matroid Designs of Prime Power Index
Local unimodularity of matrix-vector pairs
Weak k-majorization and polyhedra
Random sampling and greedy sparsification for matroid optimization problems
On bicriterion minimal spanning trees: An approximation
A fast algorithm for finding matching responses in a survey data table
On certain polytopes associated with graphs
Improved bound for the Carathéodory rank of the bases of a matroid
Hereditary systems and greedy-type algorithms.
A greedy algorithm for some classes of integer programs.
A framework for the greedy algorithm
Matroid optimisation problems with nested non-linear monomials in the objective function
A new approach for the multiobjective minimum spanning tree
On the mixed set covering, packing and partitioning polytope
Ordered weighted average optimization in multiobjective spanning tree problem
Designing matching mechanisms under constraints: an approach from discrete convex analysis
On the intersection of independence systems
Subgraph polytopes and independence polytopes of count matroids
On a modification of the VCG mechanism and its optimality
Solving the linear matroid parity problem as a sequence of matroid intersection problems
Solving combinatorial problems with combined min-max-min-sum objective and applications
Strong lower bounds for the prize collecting Steiner problem in graphs
Sufficient regularity conditions for common transversals
The application of automated reasoning to formal models of combinatorial optimization
Periodic network optimization with different arc frequencies
Simple push-relabel algorithms for matroids and submodular flows
Computing knapsack solutions with cardinality robustness
A new greedy algorithm for the quadratic assignment problem
Geometric lattice structure of covering-based rough sets through matroids
Parametric monotone function maximization with matroid constraints
Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids
Matroid optimization problems with monotone monomials in the objective
Present-biased optimization
The submodularity of two-stage stochastic maximum-weight independent set problems
On some algorithmic aspects of hypergraphic matroids
General bounds for incremental maximization
Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
The generalized dependency constrained spanning tree problem
Reinforcement learning explains various conditional cooperation
Interpretable exact linear reductions via positivity
Two-stage stochastic max-weight independent set problems
A LP-based approximation algorithm for generalized traveling salesperson path problem
Formal barriers to simple algorithms for the matroid secretary problem
Sufficient conditions for the optimality of the greedy algorithm in greedoids
Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem
Error estimation in reduced basis method for systems with time-varying and nonlinear boundary conditions
Dynamic intersection of multiple implicit Dantzig-Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem
Packing of arborescences with matroid constraints via matroid intersection
Decorous combinatorial lower bounds for row layout problems
Fair-by-design matching
Tropical Kirchhoff's formula and postoptimality in matroid optimization
New polyhedral and algorithmic results on greedoids
The minimum area spanning tree problem: formulations, Benders decomposition and branch-and-cut algorithms
A correct response model in knowledge structure theory
A branch and cut algorithm for minimum spanning trees under conflict constraints
A computational study for common network design in multi-commodity supply chains
Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem
Exact and approximation algorithms for weighted matroid intersection
Modeling and solving the angular constrained minimum spanning tree problem
Four operators of rough sets generalized to matroids and a matroidal method for attribute reduction
Approximate tradeoffs on weighted labeled matroids
The recoverable robust spanning tree problem with interval costs is polynomially solvable
Matroid representation of clique complexes
Least and most colored bases
Collision-free network exploration
Connectedness of graphs and its application to connected matroids through covering-based rough sets
Modularity and greed in double auctions
Approximating the least core value and least core of cooperative games with supermodular costs
Characterizing acyclic graphs by labeling edges
Complete description for the spanning tree problem with one linearised quadratic term
Quasi-concave functions on meet-semilattices
Using Lagrangian dual information to generate degree constrained spanning trees

This page was built for publication: Matroids and the greedy algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5668601)