Matroids and the greedy algorithm
From MaRDI portal
Publication:5668601
DOI10.1007/BF01584082zbMath0253.90027DBLPjournals/mp/Edmonds71OpenAlexW1991528957WikidataQ56387956 ScholiaQ56387956MaRDI QIDQ5668601
Publication date: 1971
Published in: Mathematical Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01584082
Related Items (only showing first 100 items - show all)
A framework for the greedy algorithm ⋮ The 2-quasi-greedy algorithm for cardinality constrained matroid bases ⋮ Knapsack polytopes: a survey ⋮ The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm ⋮ A Mazur-Orlicz type theorem for submodular set functions ⋮ Extended formulations for sparsity matroids ⋮ Evolutionary algorithms and matroid optimization problems ⋮ A greedy algorithm for hereditary set systems and a generalization of the Rado-Edmonds characterization of matroids ⋮ Matroid optimisation problems with nested non-linear monomials in the objective function ⋮ On bicriterion minimal spanning trees: An approximation ⋮ A new approach for the multiobjective minimum spanning tree ⋮ Lower bounds and exact algorithms for the quadratic minimum spanning tree problem ⋮ On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree ⋮ Reconstructing binary matrices with timetabling constraints ⋮ Generalized polymatroids and submodular flows ⋮ Polyhedra of regular p-nary group problems ⋮ A fast algorithm for finding matching responses in a survey data table ⋮ 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 ⋮ Two new perspectives on multi-stage group testing ⋮ Periodic network optimization with different arc frequencies ⋮ Simple push-relabel algorithms for matroids and submodular flows ⋮ Computing knapsack solutions with cardinality robustness ⋮ Job distribution algorithms ⋮ Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound ⋮ On certain polytopes associated with graphs ⋮ Characterizing and recognizing generalized polymatroids ⋮ The greedy algorithm for partially ordered sets ⋮ A combinatorial optimization problem: optimal generalized cycle bases ⋮ A heuristic to generate rank-1 GMI cuts ⋮ Bases axioms and circuits axioms for fuzzifying matroids ⋮ A comparative study of heuristics for a two-level routing-location problem ⋮ Improved bound for the Carathéodory rank of the bases of a matroid ⋮ A new greedy algorithm for the quadratic assignment problem ⋮ Nullity-based matroid of rough sets and its application to attribute reduction ⋮ Discrete extremal problems ⋮ Cardinality constrained combinatorial optimization: complexity and polyhedra ⋮ Hereditary systems and greedy-type algorithms. ⋮ Geometric lattice structure of covering-based rough sets through matroids ⋮ On the budget-restricted max flow problem ⋮ A greedy algorithm for some classes of integer programs. ⋮ An analysis of the greedy algorithm for partially ordered sets ⋮ Covering cycle matroid ⋮ Greedy algorithms and poset matroids ⋮ The image of weighted combinatorial problems ⋮ On the \(K\)th best base of a matroid ⋮ Faster algorithms for security games on matroids ⋮ Graph and matrix approaches to rough sets through matroids ⋮ On the diameter of convex polytopes ⋮ Bases-cobases graphs and polytopes of matroids ⋮ On the mixed set covering, packing and partitioning polytope ⋮ An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem ⋮ Stable sets versus independent sets ⋮ Ordered weighted average optimization in multiobjective spanning tree problem ⋮ New performance guarantees for the greedy maximization of submodular set functions ⋮ Analysis of the Held-Karp lower bound for the asymmetric TSP ⋮ The convex hull of two core capacitated network design problems ⋮ Designing matching mechanisms under constraints: an approach from discrete convex analysis ⋮ Cutting planes in integer and mixed integer programming ⋮ Matroid base polytope decomposition ⋮ Randomized priority algorithms ⋮ Two algorithms for matroids ⋮ Duality between quasi-concave functions and monotone linkage functions ⋮ A combinatorial ranking problem ⋮ Two easy duality theorems for product partial orders ⋮ On the intersection of independence systems ⋮ Subgraph polytopes and independence polytopes of count matroids ⋮ Reformulations and solution algorithms for the maximum leaf spanning tree problem ⋮ On a modification of the VCG mechanism and its optimality ⋮ An unbounded matroid intersection polyhedron ⋮ Matroid Designs of Prime Power Index ⋮ A simple greedy algorithm for a class of shuttle transportation problems ⋮ Local unimodularity of matrix-vector pairs ⋮ A new algorithm for the intersection of a line with the independent set polytope of a matroid ⋮ Extended formulations, nonnegative factorizations, and randomized communication protocols ⋮ A general model for matroids and the greedy algorithm ⋮ The \(S\)-digraph optimization problem and the greedy algorithm ⋮ Solving the linear matroid parity problem as a sequence of matroid intersection problems ⋮ Heuristically guided algorithm for k-parity matroid problems ⋮ Solving combinatorial problems with combined min-max-min-sum objective and applications ⋮ Strong lower bounds for the prize collecting Steiner problem in graphs ⋮ On matroid parity and matching polytopes ⋮ Priority algorithms for graph optimization problems ⋮ Weak \(k\)-majorization and polyhedra ⋮ Random sampling and greedy sparsification for matroid optimization problems ⋮ The nestedness property of the convex ordered median location problem on a tree ⋮ Sufficient regularity conditions for common transversals ⋮ 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 note on Frank's generalized polymatroids ⋮ On the number of common bases of two matroids ⋮ Total weak unimodularity: Testing and applications ⋮ The application of automated reasoning to formal models of combinatorial optimization ⋮ A note on matchings and separability ⋮ Path-closed sets ⋮ An algorithm for finding a matroid basis which maximizes the product of the weights of the elements ⋮ Pairwise kidney exchange ⋮ Non delayed relax-and-cut algorithms
Cites Work
This page was built for publication: Matroids and the greedy algorithm
