On greedy algorithms that succeed. (English) Zbl 0601.90111
Surveys in combinatorics 1985, Pap. 10th Br. Combin. Conf., Glasgow/Scotl. 1985, Lond. Math. Soc. Lect. Note Ser. 103, 97-112 (1985).
[For the entire collection see Zbl 0561.00003.]
The author surveys linear programming problems for which greedy type algorithms yield an optimal solution. Three classes of problems are considered. The first class comprises transportation problems with the Monge-property. As applications the greedy-coloring of intersection graphs and a graph partitioning problem are mentioned. Secondly a slight modification (due to Kornblut) of LPs generated by matroids is described. The third class starts from problems with the ”consecutive 1’s-property” (i.e. the 1-entries in each row of the coefficient matrix occur consecutively) and leads to problems with ”box-greedy” coefficient matrices. Moreover connections between these problems, shortest path problems and flows in series-parallel networks are discussed.
The author surveys linear programming problems for which greedy type algorithms yield an optimal solution. Three classes of problems are considered. The first class comprises transportation problems with the Monge-property. As applications the greedy-coloring of intersection graphs and a graph partitioning problem are mentioned. Secondly a slight modification (due to Kornblut) of LPs generated by matroids is described. The third class starts from problems with the ”consecutive 1’s-property” (i.e. the 1-entries in each row of the coefficient matrix occur consecutively) and leads to problems with ”box-greedy” coefficient matrices. Moreover connections between these problems, shortest path problems and flows in series-parallel networks are discussed.
Reviewer: R.E.Burkard
MSC:
90C10 | Integer programming |
90B10 | Deterministic network models in operations research |
05C35 | Extremal problems in graph theory |