A greedy algorithm for solving a certain class of linear programmes

DOI10.1007/BF01580137zbMath0297.90050OpenAlexW2087266578MaRDI QIDQ4051883

Frank D. J. Dunstan, Dominic J. A. Welsh

Publication date: 1973

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

Full work available at URL: https://doi.org/10.1007/bf01580137

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Linear programming (90C05)

Related Items

Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, On \(0,\pm 1\) matrices, odd vectors, and bisubmodular polyhedra, The delta-sum of matching delta-matroids, Coverings and delta-coverings, The greedy algorithm for partially ordered sets, Discrete extremal problems, Simultaneous selection, The Orthant Non-Interaction Theorem for Certain Combinatorial Polyhedra and its Implications in the Intersection and the Dilworth Truncation of Bisubmodular Functions, Representability of \(\bigtriangleup\)-matroids over \(GF(2)\), \(b\)-matching degree-sequence polyhedra, Polynomial combinatorial algorithms for skew-bisubmodular function minimization, Discordant Voting Processes on Finite Graphs, Greedy systems of linear inequalities and lexicographically optimal solutions, On structures of bisubmodular polyhedra, Polybasic polyhedra: Structure of polyhedra with edge vectors of support size at most 2, Signed ring families and signed posets, Generalized skew bisubmodularity: a characterization and a min-max theorem, Parametric bisubmodular function minimization and its associated signed ring family

Cites Work

• On the shortest spanning subtree of a graph and the traveling salesman problem
• Note on Independence Functions
• Optimal assignments in an ordered set: An application of matroid theory
• Unnamed Item
• Unnamed Item
• Unnamed Item