Matroids and the greedy algorithm

DOI10.1007/BF01584082zbMath0253.90027WikidataQ56387956 ScholiaQ56387956MaRDI QIDQ5668601

Publication date: 1971

Published in: Mathematical Programming (Search for Journal in Brave)

90C05: Linear programming

Related Items

Revised Greedy algorithm for formation of a minimal cycle basis of a graph, The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm, Properties of vertex packing and independence system polyhedra, Blocking and anti-blocking pairs of polyhedra, Persistency in combinatorial optimization problems on matroids, Active orders for matroid bases, A comparison of Steiner tree relaxations, Two easy duality theorems for product partial orders, Bases-cobases graphs and polytopes of matroids, Stable sets versus independent sets, The convex hull of two core capacitated network design problems, Cutting planes in integer and mixed integer programming, Heuristically guided algorithm for k-parity matroid problems, 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, A note on matchings and separability, Path-closed sets, Pairwise kidney exchange, Non delayed relax-and-cut algorithms, Job distribution algorithms, On the \(K\)th best base of a matroid, 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, 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, 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, Matroid representation of clique complexes, Least and most colored bases, Quasi-concave functions on meet-semilattices, Using Lagrangian dual information to generate degree constrained spanning trees, \(k\)-edge connected polyhedra on series-parallel graphs, A greedy algorithm for maximizing a linear objective function, A new exchange property for matroids and its application to max-min-problems, Unlabelled Partition Systems: Optimization and Complexity, Integer Rounding for Polymatroid and Branching Optimization Problems, The traveling salesman problem on a graph and some related integer polyhedra, New applications of partial orders, Connected and alternating vectors: Polyhedra and algorithms, On approximate algorithms for combinatorial linear maximization problems, Greedy Families for Linear Objective Functions, Faces for a linear inequality in 0–1 variables, Matroid intersection algorithms, Einige Aspekte in der Zuordnungstheorie, Bottleneck linear programming, Transversal matroid intersections and related packings, An analysis of approximations for maximizing submodular set functions—I, The adjacency relation on the traveling salesman polytope is NP-Complete, The Held—Karp algorithm and degree-constrained minimum 1-trees

Cites Work