Matroids and the greedy algorithm
From MaRDI portal
Publication:5668601
DOI10.1007/BF01584082zbMath0253.90027OpenAlexW1991528957WikidataQ56387956 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
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, Multi-objective matroid optimization with ordinal weights, Stronger path‐based extended formulation for the Steiner tree problem, Shadows of Newton polytopes, On a certified VMS-Smagorinsky reduced basis model with LPS pressure stabilisation, Polyhedral results and stronger Lagrangean bounds for stable spanning trees, Unified Greedy Approximability beyond Submodular Maximization, Unified greedy approximability beyond submodular maximization, Reconfiguration of time-respecting arborescences, Geodesic property of greedy algorithms for optimization problems on jump systems and delta-matroids, Linear-size formulations for connected planar graph partitioning and political districting, An ‘All pairs shortest paths’ distributed algorithm using 2n 2 messages, Projection-based reduced order models for parameterized nonlinear time-dependent problems arising in cardiac mechanics, Quantum algorithms for learning hidden strings with applications to matroid problems, Diverse collections in matroids and graphs, Unnamed Item, Persistency in combinatorial optimization problems on matroids, Active orders for matroid bases, A comparison of Steiner tree relaxations, A rough set approach to the characterization of transversal matroids, Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond, The recoverable robust spanning tree problem with interval costs is polynomially solvable, The generalized dependency constrained spanning tree problem, Greedy Families for Linear Objective Functions, New applications of partial orders, Algorithm for constraint partial inverse matroid problem with weight increase forbidden, Reinforcement learning explains various conditional cooperation, Interpretable exact linear reductions via positivity, Matroid representation of clique complexes, Least and most colored bases, On the Structure of Optimal Greedy Computation (for Job Scheduling), 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, Collision-free network exploration, Toward an Automatic Approach to Greedy Algorithms, 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, Connectedness of graphs and its application to connected matroids through covering-based rough sets, On the extension complexity of scheduling polytopes, A Discrete Convex Min-Max Formula for Box-TDI Polyhedra, Error estimation in reduced basis method for systems with time-varying and nonlinear boundary conditions, Revised Greedy algorithm for formation of a minimal cycle basis of a graph, Dynamic intersection of multiple implicit Dantzig-Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem, Modularity and greed in double auctions, Two-echelon supply chain network design with trade credit, Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint, Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid, Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes, Extended formulations for matroid polytopes through randomized protocols, Polyhedra and optimization in connection with a weak majorization ordering, Problems on independence systems solvable by the greedy algorithm, Packing of arborescences with matroid constraints via matroid intersection, Decorous combinatorial lower bounds for row layout problems, An LP-based approximation algorithm for the generalized traveling salesman path problem, Optimal Mechanism Design for a Sequencing Problem with Two-Dimensional Types, Hepp's bound for Feynman graphs and matroids, Blocking and anti-blocking pairs of polyhedra, Interactive optimization of submodular functions under matroid constraints, Graphic Submodular Function Minimization: A Graphic Approach and Applications, The Greedy Algorithm and the Cohen-Macaulay Property of Rings, Graphs and Toric Projective Curves, Fair-by-design matching, Static Routing in Stochastic Scheduling: Performance Guarantees and Asymptotic Optimality, Approximating the least core value and least core of cooperative games with supermodular costs, Tropical Kirchhoff's formula and postoptimality in matroid optimization, Faces for a linear inequality in 0–1 variables, Characterizing acyclic graphs by labeling edges, New polyhedral and algorithmic results on greedoids, Complete description for the spanning tree problem with one linearised quadratic term, Matroid intersection algorithms, Einige Aspekte in der Zuordnungstheorie, The minimum area spanning tree problem: formulations, Benders decomposition and branch-and-cut algorithms, On the cardinality constrained matroid polytope, Unnamed Item, A correct response model in knowledge structure theory, Quasi-concave functions on meet-semilattices, Extended formulations in combinatorial optimization, Bottleneck linear programming, A branch and cut algorithm for minimum spanning trees under conflict constraints, A computational study for common network design in multi-commodity supply chains, Transversal matroid intersections and related packings, Parametric monotone function maximization with matroid constraints, Extended formulations in combinatorial optimization, Using Lagrangian dual information to generate degree constrained spanning trees, 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, Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem, Clique-connecting forest and stable set polytopes, Matchings in connection with ground delay program planning, An analysis of approximations for maximizing submodular set functions—I, The adjacency relation on the traveling salesman polytope is NP-Complete, Algorithms for Euclidean Degree Bounded Spanning Tree Problems, The Held—Karp algorithm and degree-constrained minimum 1-trees, Robust Independence Systems, Approximation Limitations of Pure Dynamic Programming, Connected and alternating vectors: Polyhedra and algorithms, Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids, The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm, Matroid optimization problems with monotone monomials in the objective, On approximate algorithms for combinatorial linear maximization problems, Exact and approximation algorithms for weighted matroid intersection, Unnamed Item, A New Formulation for Spanning Trees, Monge Properties, Optimal Greedy Policies, and Policy Improvement for the Dynamic Stochastic Transportation Problem, \(k\)-edge connected polyhedra on series-parallel graphs, Present-biased optimization, Modeling and solving the angular constrained minimum spanning tree problem, Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal, Four operators of rough sets generalized to matroids and a matroidal method for attribute reduction, Integer Rounding for Polymatroid and Branching Optimization Problems, The submodularity of two-stage stochastic maximum-weight independent set problems, The traveling salesman problem on a graph and some related integer polyhedra, Approximate tradeoffs on weighted labeled matroids, On some algorithmic aspects of hypergraphic matroids, Market Pricing for Matroid Rank Valuations, On the Complexity of Inverse Mixed Integer Linear Optimization, Unnamed Item, Properties of vertex packing and independence system polyhedra, General bounds for incremental maximization
Cites Work
