A General Class of Greedily Solvable Linear Programs

References

• Adler I., Hoffman A. J., Shamir R. Monge and feasibility sequences in general flow problems. Discrete Appl. Math. (1993) 44:21–38Crossref, Google Scholar
• Adler I., Shamir R., Du D.-Z., Pardalos P. M. Greedily solvable transportation networks and edge-guided vertex elimination. Network Optimization Problems: Algorithms, Applications and Complexity (1993) (World Scientific)1–22Crossref, Google Scholar
• Aggarwal A., Klawe M. M. Applications of generalized matrix searching to geometric algorithms. Discrete Appl. math. (1990) 27:3–23Crossref, Google Scholar
• Aggarwal A., Klawe M. M., Moran S., Shor P., Wilber R. Geometric applications of a matrix-searching algorithm. Algorithmica (1987) 2:195–208Crossref, Google Scholar
• Aggarwal A., Park J. K. Sequential searching in multi-dimensional monotone arrays. (1989a) . Research report RC 15128, IBM T. J. Watson Research Center, Yorktown HeightsGoogle Scholar
• Aggarwal A., Park J. K. Parallel searching in multi-dimensional monotone arrays. (1989b) . Research report RC 14826, IBM T. J. Watson Research Center, Yorktown HeightsGoogle Scholar
• Aggarwal A., Park J. K. Improved algorithms for economic lot-size problems. Oper. Res. (1993) 41:549–571Link, Google Scholar
• Balas E., Saltzman M. J. Facets of the three-index assignment polytope. Discrete Appl. Math. (1989) 23:201–229Crossref, Google Scholar
• Bandelt H. J., Crama Y., Spieksma F. C. R. Approximation algorithms for multi-dimensional assignment problems with decomposable costs. Discrete Appl. Math. (1994) 49:25–50Crossref, Google Scholar
• Bein W. W., Brucker P., Pathak P. K. Monge properties in higher dimensions. (1991) . Preprint 134, Universität OsnabrückGoogle Scholar
• Bein W. W., Brucker P., Park J. K., Pathak P. K. A Monge property for the d-dimensional transportation problem. Discrete Appl. Math. (1995) 58:97–109Crossref, Google Scholar
• Birkhoff G.Lattice Theory (1967) 3rd ed.(Amer. Math. Soc. Colloq. Publ., 25. American Mathematical Society, Providence, RI) Google Scholar
• Burkard R. E., Klinz B., Rudolf R. Perspectives of Monge properties in optimization. Discrete Appl. Math. (1996) 70:95–161Crossref, Google Scholar
• Crama Y., Spieksma F. C. R. Approximation algorithms for three-dimensional assignment problems with triangle inequalities. Eur. J. Oper. Res. (1992) 60:273–279Crossref, Google Scholar
• Dietrich B. L. Monge sequences, antimatroids, and the transportation problem with forbidden arcs. Linear Algebra Appl. (1990) 39:133–145Crossref, Google Scholar
• Edmonds J., Guy R., et al. Submodular functions, matroids and certain polyhedra. Combinatorial Structures and Their Applications (1970) (Gordon and Breach, New York) 69–87Google Scholar
• Edmonds J. Matroids and the greedy algorithm. Math. Programming (1971) 1:127–136Crossref, Google Scholar
• Edmonds J., Giles R. A min-max relation for submodular functions on graphs. Ann. Discrete Math. (1974) 1:185–204Crossref, Google Scholar
• Faigle U., Kern W. Submodular linear programs on forests. Math. Programming (1996) 72:195–206(Original manuscript: Memorandum No. 1163, Faculty of Applied Mathematics, University of Twente, September. 1993.)Crossref, Google Scholar
• Frank A., Tardos É. Generalized polymatroids and submodular flows. Math. Programming (1988) 42:489–563Crossref, Google Scholar
• Frieze A. M., Yadegar J. An algorithm for solving 3-dimensional assignment problems with applications to scheduling a teaching practice. J. Oper. Res. Soc. (1981) 32:989–995Crossref, Google Scholar
• Fujishige S.Submodular Functions and Optimization (1991) (North-Holland, Amsterdam) Google Scholar
• Fujishige S., Tomizawa N. A note on submodular functions on distributive lattices. J. Oper. Res. Soc. Japan (1983) 26:309–318Google Scholar
• Gilmore P. C., Lawler E. L., Shmoys D. B., Lawler E. L., et al. Well-solved special cases. The Traveling Salesman Problem (1985) (Wiley, Chichester) Google Scholar
• Granot F., Veinott A. F. Substitutes, complements and ripples in network flows. Math. Oper. Res. (1985) 10:471–497Link, Google Scholar
• Haley K. B. The multi-index problem. Oper. Res. (1962) 11:368–379Link, Google Scholar
• Hoffman A. J., Klee V. On simple linear programming problems. Convexity: Proc. Seventh Sympos. in Pure Mathematics (1963) 7Proceedings of Symposia in Pure Mathematics(American Mathematical Society, Providence, RI) 317–327Google Scholar
• Hoffman A. J. A generalization of max-flow min-cut. Math. Programming (1974) 6:352–359Crossref, Google Scholar
• Hoffman A. J., Anderson I. On greedy algorithms that succeed. Surveys in Combinatorics (1985) (Cambridge University Press, Cambridge) 97–112Crossref, Google Scholar
• Klawe M. M. Superlinear bounds for matrix searching problems. J. Algorithms (1992) 13:55–78Crossref, Google Scholar
• Korte B., Lovász L., Schrader R.Greedoids (1991) (Springer, Berlin) Crossref, Google Scholar
• Korsnikov A. D. Planar three-index transportation problems with dominating index. Z OR—Zeitschrift für Oper. Res. (1988) 32:29–33Crossref, Google Scholar
• Larmore L. L., Schieber B. On-line dynamic programming with applications to the prediction of RNA secondary structure. J. Algorithms (1991) 12:490–515Crossref, Google Scholar
• Lovász L., Bachem A., et al. Submodular functions and convexity. Mathematical Programming—The State of The Art (1983) (Springer, Berlin) 235–257Crossref, Google Scholar
• Monge G. Mémoire sur la théorie des déblais et remblais. Mémoires de Mathematiques et de Physique (1781) 666–704Google Scholar
• Nemhauser G. L., Wolsey L. A.Integer and Combinatorial Optimization (1988) (Wiley, Chichester) Crossref, Google Scholar
• Park J. K. A special case of the n-vertex traveling salesman problem that can be solved in O(n) time. Inform. Processing Lett. (1991) 40:247–254Crossref, Google Scholar
• Pierskalla W. P. The multidimensional assignment problem. Oper. Res. (1968) 16:422–431Link, Google Scholar
• Queyranne M., Spieksma F. C. R. Approximation algorithms for multi-index transportation problems with decomposable costs. Discrete Appl. Math. (1997) 76:239–253Crossref, Google Scholar
• Queyranne M., Spieksma F. C. R., Tardella F., Rinaldi G., Wolsey L. A general class of greedily solvable linear programs. Integer Programming and Combinatorial Optimization (1993) 385–3993, Proc. Third IPCO Conf., CORE, Louvain-la-Neuve, May 1993Google Scholar
• Rudolf R. (1992) . Personal communicationGoogle Scholar
• Sankoff D., Kruskal J. B.Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison (1983) (Addison-Wesley, Reading, MA) Google Scholar
• Shamir R., Dietrich B. L. Characterization and algorithms for greedily solvable transportation problems. Proc. 1st ACM/SIAM Sympos. on Discrete Algorithms (1990) 358–366Google Scholar
• Tamir A. The least element property of center location on tree networks with applications to distance and precedence constrained problems. Math. Programming (1993) 62:475–496Crossref, Google Scholar
• Topkis D. M. Minimizing a submodular function on a lattice. Oper. Res. (1978) 26:305–321Link, Google Scholar
• van der Veen J. A., van Dal R. Solvable cases of the no-wait flow-shop scheduling problem. J. Oper. Res. Soc. (1991) 42:971–980Crossref, Google Scholar
• Veinott A. F. Representation of general and polyhedral subsemilattices and sublattices of product spaces. Linear Algebra Appl. (1989) 114/115:681–704Crossref, Google Scholar
• Wu X. Optimal quantization by matrix searching. J. Algorithms (1991) 12:663–673Crossref, Google Scholar
• Yao F. F. Efficient dynamic programming using quadrangle inequalities. Proc. 12th ACM Sympos. on Theory of Comput. (1980) 429–435Crossref, Google Scholar
• Yemelichev V. A., Kovalev M. M., Kratsov M. K.Polytopes, Graphs and Optimisation (1984) (Cambridge University Press, Cambridge) Google Scholar