Matroids and the greedy algorithm
From MaRDI portal
Publication:5668601
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, 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, 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, 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, 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, \(k\)-edge connected polyhedra on series-parallel graphs, A greedy algorithm for maximizing a linear objective function, 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
