{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T21:22:47Z","timestamp":1773868967514,"version":"3.50.1"},"reference-count":142,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1996,9,1]],"date-time":"1996-09-01T00:00:00Z","timestamp":841536000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":6163,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[1996,9]]},"DOI":"10.1016\/0166-218x(95)00103-x","type":"journal-article","created":{"date-parts":[[2003,4,7]],"date-time":"2003-04-07T17:19:33Z","timestamp":1049735973000},"page":"95-161","source":"Crossref","is-referenced-by-count":205,"title":["Perspectives of Monge properties in optimization"],"prefix":"10.1016","volume":"70","author":[{"given":"Rainer E.","family":"Burkard","sequence":"first","affiliation":[]},{"given":"Bettina","family":"Klinz","sequence":"additional","affiliation":[]},{"given":"R\u00fcdiger","family":"Rudolf","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0166-218X(95)00103-X_BIB1","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0166-218X(93)90220-I","article-title":"Monge and feasibility sequences in general flow problems","volume":"44","author":"Adler","year":"1993","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB2","series-title":"Network Optimization Problems: Algorithms, Applications and Complexity","first-page":"1","article-title":"Greedily solvable transportation networks and edge-guided vertex elimination","author":"Adler","year":"1993"},{"key":"10.1016\/0166-218X(95)00103-X_BIB3","series-title":"Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science","first-page":"583","article-title":"Efficient minimum cost matching using quadrangle inequality","author":"Aggarwal","year":"1992"},{"key":"10.1016\/0166-218X(95)00103-X_BIB4","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF01840359","article-title":"Geometric applications of a matrix-searching algorithm","volume":"2","author":"Aggarwal","year":"1987","journal-title":"Algorithmica"},{"key":"10.1016\/0166-218X(95)00103-X_BIB5","series-title":"Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science","first-page":"497","article-title":"Notes on searching in multidimensional monotone arrays","author":"Aggarwal","year":"1988"},{"key":"10.1016\/0166-218X(95)00103-X_BIB6","article-title":"Sequential searching in multidimensional monotone arrays","author":"Aggarwal","year":"1989"},{"key":"10.1016\/0166-218X(95)00103-X_BIB7","article-title":"Parallel searching in multidimensional monotone arrays","author":"Aggarwal","year":"1989"},{"key":"10.1016\/0166-218X(95)00103-X_BIB8","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1287\/opre.41.3.549","article-title":"Improved algorithms for economic lot-size problems","volume":"41","author":"Aggarwal","year":"1993","journal-title":"Oper. Res."},{"key":"10.1016\/0166-218X(95)00103-X_BIB9","series-title":"More applications of Monge-array techniques to economic lot-size problems","author":"Aggarwal","year":"1993"},{"key":"10.1016\/0166-218X(95)00103-X_BIB10","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF02574380","article-title":"Finding a minimum weight K-link path in graphs with Monge property and applications","volume":"12","author":"Aggarwal","year":"1994","journal-title":"Discrete Comput. Geometry"},{"key":"10.1016\/0166-218X(95)00103-X_BIB11","first-page":"13","article-title":"Selection in monotone matrices and kth nearest neighbors","volume":"824","author":"Agarwal","year":"1994"},{"key":"10.1016\/0166-218X(95)00103-X_BIB12","first-page":"401","article-title":"Algorithms for finding extremum of a linear form on the set of all cycles in special cases","volume":"12","author":"Aizenshtat","year":"1968","journal-title":"Dokl. Akad. Nauk BSSR"},{"key":"10.1016\/0166-218X(95)00103-X_BIB13_1","first-page":"80","article-title":"Special cases of traveling salesman problems","volume":"4","author":"Aizenshtat","year":"1978","journal-title":"Kibernetika"},{"key":"10.1016\/0166-218X(95)00103-X_BIB13_2","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/BF01069839","volume":"14","author":"Aizenshtat","year":"1979","journal-title":"Cybernetics"},{"key":"10.1016\/0166-218X(95)00103-X_BIB14","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1016\/0024-3795(89)90487-4","article-title":"An algorithm for the detection and construction of Monge sequences","volume":"114\/115","author":"Alon","year":"1989","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/0166-218X(95)00103-X_BIB15","article-title":"Linear Programming in Infinite-Dimensional Spaces: Theory and Applications","author":"Anderson","year":"1987"},{"key":"10.1016\/0166-218X(95)00103-X_BIB16","doi-asserted-by":"crossref","first-page":"968","DOI":"10.1137\/0219066","article-title":"Efficient parallel algorithms for string editing and related problems","volume":"19","author":"Apostolico","year":"1990","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(95)00103-X_BIB17","series-title":"On Monge-Kantorovich problems","author":"Balinski","year":"1989"},{"key":"10.1016\/0166-218X(95)00103-X_BIB18","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1137\/0606048","article-title":"On transportation problems with upper bounds on leading rectangles","volume":"6","author":"Barnes","year":"1985","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10.1016\/0166-218X(95)00103-X_BIB19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01585157","article-title":"Series parallel composition of greedy linear programming problems","volume":"62","author":"Bein","year":"1993","journal-title":"Math. Programming"},{"key":"10.1016\/0166-218X(95)00103-X_BIB20","series-title":"Presented at the 3rd Twente Workshop on Graphs and Combinatorial Optimization","article-title":"Applications of an algebraic Monge property","author":"Bein","year":"1993"},{"key":"10.1016\/0166-218X(95)00103-X_BIB21","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0166-218X(93)E0121-E","article-title":"A Monge property for the d-dimensional transportation problem","volume":"58","author":"Bein","year":"1995","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB22","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0166-218X(85)90006-X","article-title":"Minimum cost flow algorithms for series-parallel networks","volume":"10","author":"Bein","year":"1985","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB23","article-title":"A characterization of the Monge property","author":"Bein","year":"1990"},{"key":"10.1016\/0166-218X(95)00103-X_BIB24","series-title":"Proceedings of the 23-rd Annual ACM Symposium on the Theory of Computing","first-page":"328","article-title":"Linear approximation of shortest superstrings","author":"Blum","year":"1991"},{"key":"10.1016\/0166-218X(95)00103-X_BIB25","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0020-0190(94)90101-5","article-title":"Extending the quadrangle inequality to speed-up dynamic programming","volume":"49","author":"Borchers","year":"1994","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0166-218X(95)00103-X_BIB26_1","first-page":"16","article-title":"Generalization of the results of Gilmore and Gomory on the solution of the traveling salesman problem","volume":"3","author":"Burdyuk","year":"1976","journal-title":"Izw. Akad. Nauk SSSR Tech. Kibernet"},{"key":"10.1016\/0166-218X(95)00103-X_BIB26_2","first-page":"12","volume":"14","author":"Burdyuk","year":"1976","journal-title":"Engi. Cybernet."},{"key":"10.1016\/0166-218X(95)00103-X_BIB27","first-page":"63","article-title":"Remarks on some scheduling problems with algebraic objective function","volume":"32","author":"Burkard","year":"1978","journal-title":"Methods Oper. Res."},{"key":"10.1016\/0166-218X(95)00103-X_BIB28","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0012-365X(78)90055-9","article-title":"A general Hungarian method for the algebraic transportation problem","volume":"22","author":"Burkard","year":"1978","journal-title":"Discrete Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB29","series-title":"Proceedings of the 12th IFIP Conference: System Modelling and Optimization","first-page":"153","article-title":"Assignment problems: recent solution methods and applications","volume":"84","author":"Burkard","year":"1986"},{"key":"10.1016\/0166-218X(95)00103-X_BIB30","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF02019153","article-title":"Special cases of travelling salesman problems and heuristics","volume":"6","author":"Burkard","year":"1990","journal-title":"Acta Math. Appl. Sinica"},{"key":"10.1016\/0166-218X(95)00103-X_BIB31","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0167-6377(95)00003-3","article-title":"On the role of bottleneck Monge matrices in combinatorial optimization","volume":"17","author":"Burkard","year":"1995","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/0166-218X(95)00103-X_BIB32","article-title":"Easy and hard cases of the quadratic assignment problem: a survey, manuscript","author":"Burkard","year":"1995"},{"key":"10.1016\/0166-218X(95)00103-X_BIB33","series-title":"SFB-Report No. 34","article-title":"The quadratic assignment problem with an Anti-Monge and a Toeplitz matrix: easy and hard cases","author":"Burkard","year":"1995"},{"key":"10.1016\/0166-218X(95)00103-X_BIB34","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF02253612","article-title":"Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood","volume":"54","author":"Burkard","year":"1995","journal-title":"Computing"},{"key":"10.1016\/0166-218X(95)00103-X_BIB35","article-title":"Well-solvable special cases of the TSP: A survey","author":"Burkard","year":"1995"},{"key":"10.1016\/0166-218X(95)00103-X_BIB36","series-title":"SFB \u201cOptimierung und Kontrolle\u201d","article-title":"The traveling salesman problem on permuted Monge matrices","author":"Burkard","year":"1995"},{"key":"10.1016\/0166-218X(95)00103-X_BIB37","article-title":"Axial assignment problems with decomposable cost coefficients","author":"Burkard","year":"1992"},{"key":"10.1016\/0166-218X(95)00103-X_BIB38","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0166-218X(91)90024-Q","article-title":"Efficiently solvable special cases of bottleneck travelling salesman problems","volume":"32","author":"Burkard","year":"1991","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB39","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1080\/02331939108843720","article-title":"Universal conditions for algebraic travelling salesman problems to be efficiently solvable","volume":"22","author":"Burkard","year":"1991","journal-title":"Optimization"},{"key":"10.1016\/0166-218X(95)00103-X_BIB40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BFb0120884","article-title":"Weakly admissible transformations for solving algebraic assignment and transportation problems","volume":"12","author":"Burkard","year":"1980","journal-title":"Math. Programming Study"},{"key":"10.1016\/0166-218X(95)00103-X_BIB41","series-title":"Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms","first-page":"65","article-title":"Linear and O(n log n) time minimum-cost matching algorithms for quasi-convex tours","author":"Buss","year":"1994"},{"key":"10.1016\/0166-218X(95)00103-X_BIB42","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/BF00532695","article-title":"Inequalities for Ek(X, Y) when the marginals are fixed","volume":"36","author":"Cambanis","year":"1976","journal-title":"Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und verwandte Gebiete"},{"key":"10.1016\/0166-218X(95)00103-X_BIB43","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0012-365X(90)90143-6","article-title":"On the Monge property of matrices","volume":"81","author":"Cechl\u00e1rov\u00e1","year":"1990","journal-title":"Discrete Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB44","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2787-6","article-title":"The quadratic assignment problem: special cases and relatives","author":"\u00c7ela","year":"1995"},{"key":"10.1016\/0166-218X(95)00103-X_BIB45","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1002\/net.3230230105","article-title":"Efficient parallel algorithms for bipartite permutation graphs","volume":"22","author":"Chen","year":"1993","journal-title":"Networks"},{"key":"10.1016\/0166-218X(95)00103-X_BIB46","series-title":"Issledovanie operaziy i ASU 14 Kiev","first-page":"47","article-title":"Applying dynamic programming to solving a special multi-traveling salesmen problem","author":"De\u01d0neko","year":"1979"},{"key":"10.1016\/0166-218X(95)00103-X_BIB47","series-title":"Aktualnyje Problemy EVM i programmirovanije","article-title":"On the reconstruction of specially structured matrices","author":"De\u01d0neko","year":"1979"},{"key":"10.1016\/0166-218X(95)00103-X_BIB48","series-title":"SFB \u201cOptimierung und Kontrolle\u201d","article-title":"Three easy special cases of the Euclidean travelling salesman problem","author":"De\u01d0neko","year":"1995"},{"key":"10.1016\/0166-218X(95)00103-X_BIB49","series-title":"SFB \u201cOptimierung und Kontrolle\u201d","article-title":"The recognition of permuted Supnik and incomplete Monge matrices","author":"De\u01d0neko","year":"1994"},{"key":"10.1016\/0166-218X(95)00103-X_BIB50_1","series-title":"SFB \u201cOptimierung und Kontrolle\u201d","article-title":"Sometimes travelling is easy: the master tour problem","author":"De\u01d0neko","year":"1994"},{"key":"10.1016\/0166-218X(95)00103-X_BIB50_2","first-page":"128","article-title":"An extended abstract appeared","volume":"979","author":"De\u01d0neko","year":"1995"},{"key":"10.1016\/0166-218X(95)00103-X_BIB51","first-page":"28","article-title":"A special case of travelling salesman problems","volume":"5","author":"Demidenko","year":"1976","journal-title":"Izv. Akad. Nauk. BSSR, Ser. fiz.-mat. nauk"},{"key":"10.1016\/0166-218X(95)00103-X_BIB52","series-title":"Graph-theoretic Concepts in Computer Science","first-page":"79","article-title":"Bisimplicial edges, Gaussian elimination and matchings in bipartite graphs","author":"Derigs","year":"1984"},{"key":"10.1016\/0166-218X(95)00103-X_BIB53","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0166-218X(86)90045-4","article-title":"Monge sequences and a simple assignment algorithm","volume":"15","author":"Derigs","year":"1986","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB54","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0024-3795(90)90393-Q","article-title":"Monge sequences, antimatroids and the transportation problem with forbidden arcs","volume":"139","author":"Dietrich","year":"1990","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/0166-218X(95)00103-X_BIB55","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01720146","article-title":"Reshipments and overshipments in transportation problems with minimax objective","volume":"13","author":"Eiselt","year":"1991","journal-title":"OR Spektrum"},{"key":"10.1016\/0166-218X(95)00103-X_BIB56","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0196-6774(90)90031-9","article-title":"Sequence comparison with mixed convex and concave costs","volume":"11","author":"Eppstein","year":"1990","journal-title":"J. Algorithms"},{"key":"10.1016\/0166-218X(95)00103-X_BIB57","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1287\/moor.12.4.634","article-title":"Send-and-split method for minimum-concave-cost network flows","volume":"12","author":"Erickson","year":"1987","journal-title":"Math. Oper. Res."},{"key":"10.1016\/0166-218X(95)00103-X_BIB58","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01719448","article-title":"Some recent results in the analysis of greedy algorithms for assignment problems","volume":"15","author":"Faigle","year":"1994","journal-title":"OR Spektrum"},{"key":"10.1016\/0166-218X(95)00103-X_BIB59","doi-asserted-by":"crossref","DOI":"10.1007\/BF02592089","article-title":"Submodular linear programs on forests","author":"Faigle","year":"1993"},{"key":"10.1016\/0166-218X(95)00103-X_BIB60","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1287\/mnsc.37.8.909","article-title":"A simple forward algorithm to solve general dynamic lot sizing models with n periods in O(n log n) or O(n) time","volume":"37","author":"Federgruen","year":"1991","journal-title":"Management Sci."},{"key":"10.1016\/0166-218X(95)00103-X_BIB61","series-title":"SFB \u201cOptimierung und Kontrolle\u201d","article-title":"Weak algebraic Monge arrays","author":"Fortin","year":"1995"},{"key":"10.1016\/0166-218X(95)00103-X_BIB62","first-page":"53","article-title":"Sur les tableaux de corr\u00e9lation dont les marges sont donn\u00e9es","volume":"14","author":"Frech\u00e9t","year":"1951","journal-title":"Annales de l'Universit\u00e9 de Lyon, Section A"},{"key":"10.1016\/0166-218X(95)00103-X_BIB63","first-page":"13","article-title":"Sur les tableaux de corr\u00e9lation dont les marges sont donn\u00e9es","volume":"20","author":"Frech\u00e9t","year":"1957","journal-title":"Annales de l'Universit\u00e9 de Lyon, Section A"},{"key":"10.1016\/0166-218X(95)00103-X_BIB64","first-page":"128","article-title":"On the minimization of a linear form on cycles","volume":"4","author":"Gaikov","year":"1980","journal-title":"Vestsi Akad. Navuk BSSR Ser. Fiz.-Mat. Navuk"},{"key":"10.1016\/0166-218X(95)00103-X_BIB65","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0020-0190(90)90215-J","article-title":"A linear-time algorithm for concave one-dimensional dynamic programming","volume":"33","author":"Galil","year":"1990","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0166-218X(95)00103-X_BIB66","series-title":"The Traveling Salesman Problem","first-page":"87","article-title":"Well-solved special cases","author":"Gilmore","year":"1985"},{"key":"10.1016\/0166-218X(95)00103-X_BIB67","article-title":"Subcones of submodular functions (subclasses of Monge matrices)","author":"Girlich","year":"1994"},{"key":"10.1016\/0166-218X(95)00103-X_BIB68","series-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic","year":"1980"},{"key":"10.1016\/0166-218X(95)00103-X_BIB69","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1002\/jgt.3190020209","article-title":"Perfect elimination and chordal bipartite graphs","volume":"2","author":"Golumbic","year":"1978","journal-title":"J. Graph Theory"},{"key":"10.1016\/0166-218X(95)00103-X_BIB70","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/net.3230150107","article-title":"A minimum concave-cost dynamic network flow problem with an application to lot-sizing","volume":"15","author":"Graves","year":"1985","journal-title":"Networks"},{"key":"10.1016\/0166-218X(95)00103-X_BIB71","first-page":"375","article-title":"Design (with analysis) of efficient algorithms","volume":"Vol. 3","author":"Gusfield","year":"1992"},{"key":"10.1016\/0166-218X(95)00103-X_BIB72","series-title":"Inequalities","author":"Hardy","year":"1952"},{"key":"10.1016\/0166-218X(95)00103-X_BIB73","doi-asserted-by":"crossref","first-page":"628","DOI":"10.1137\/0216043","article-title":"The least weight subsequence problem","volume":"16","author":"Hirschberg","year":"1987","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(95)00103-X_BIB74","first-page":"179","article-title":"Ma\u03b2stabsinvariante Korrelationstheorie","volume":"5","author":"Hoeffding","year":"1940","journal-title":"Schriften des Mathematischen Instituts und des Instituts f\u00fcr Angewandte Mathematik der Universit\u00e4t Berlin"},{"key":"10.1016\/0166-218X(95)00103-X_BIB75","series-title":"Proceedings of Symposia in Pure Mathematics","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1090\/pspum\/007\/0157778","article-title":"On simple linear programming problems","volume":"Vol. VII","author":"Hoffman","year":"1963"},{"key":"10.1016\/0166-218X(95)00103-X_BIB76","series-title":"Surveys in combinatorics","first-page":"97","article-title":"On greedy algorithms that succeed","author":"Hoffman","year":"1985"},{"key":"10.1016\/0166-218X(95)00103-X_BIB77","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/BF01580730","article-title":"On greedy algorithms for series parallel graphs","volume":"40","author":"Hoffman","year":"1988","journal-title":"Math. Programming"},{"key":"10.1016\/0166-218X(95)00103-X_BIB78","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF01585166","article-title":"Staircase transportation problems with superadditive rewards and cumulative capacities","volume":"62","author":"Hoffman","year":"1993","journal-title":"Math. Programming"},{"key":"10.1016\/0166-218X(95)00103-X_BIB79","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/nav.3800010110","article-title":"Optimal two and three-stage production schedules with setup times included","volume":"1","author":"Johnson","year":"1954","journal-title":"Naval Res. Logistics Quart."},{"key":"10.1016\/0166-218X(95)00103-X_BIB80","doi-asserted-by":"crossref","first-page":"1000","DOI":"10.4153\/CJM-1975-104-6","article-title":"Edgeconvex circuits and the traveling salesman problem","volume":"27","author":"Kalmanson","year":"1975","journal-title":"Can. J. Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB81","first-page":"227","article-title":"On the transfer of masses","volume":"37","author":"Kantorovich","year":"1942","journal-title":"Doklady Akad. Nauk. USSR"},{"key":"10.1016\/0166-218X(95)00103-X_BIB82","first-page":"225","article-title":"On a problem of Monge","volume":"3","author":"Kantorovich","year":"1948","journal-title":"Uspekhi Mat. Nauk."},{"key":"10.1016\/0166-218X(95)00103-X_BIB83","volume":"Vol. 1","author":"Karlin","year":"1968"},{"key":"10.1016\/0166-218X(95)00103-X_BIB84","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0012-365X(75)90014-X","article-title":"Two special cases of the assignment problem","volume":"13","author":"Karp","year":"1975","journal-title":"Discrete Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB85","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1137\/0403009","article-title":"An almost linear time algorithm for generalized matrix searching","volume":"3","author":"Klawe","year":"1990","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB86","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0166-218X(94)00054-H","article-title":"Permuting matrices to avoid forbidden submatrices","volume":"60","author":"Klinz","year":"1995","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB87","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0166-218X(94)00019-A","article-title":"On the recognition of permuted bottleneck Monge matrices","volume":"63","author":"Klinz","year":"1995","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB88","series-title":"Greedoids","author":"Korte","year":"1991"},{"key":"10.1016\/0166-218X(95)00103-X_BIB89","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/BF02090398","article-title":"Selection and sorting in totally monotone matrices","volume":"24","author":"Kravets","year":"1991","journal-title":"Math. Systems Theory"},{"key":"10.1016\/0166-218X(95)00103-X_BIB90","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0196-6774(91)90016-R","article-title":"On-line dynamic programming with applications to the prediction of RNA secondary structure","volume":"12","author":"Larmore","year":"1991","journal-title":"J. Algorithms"},{"key":"10.1016\/0166-218X(95)00103-X_BIB91","doi-asserted-by":"crossref","first-page":"176","DOI":"10.2307\/2307574","article-title":"An inequality for rearrangements","volume":"60","author":"Lorentz","year":"1953","journal-title":"Amer. Math. Monthly"},{"key":"10.1016\/0166-218X(95)00103-X_BIB92","series-title":"Mathematical Programming; The State of the Art, Bonn 1982","first-page":"235","article-title":"Submodular functions and convexity","author":"Lov\u00e1sz","year":"1983"},{"key":"10.1016\/0166-218X(95)00103-X_BIB93","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1142\/S0218195993000087","article-title":"Improved selection in totally monotone arrays","volume":"3","author":"Mansour","year":"1993","journal-title":"Int. J. Comput. Geometry Appl."},{"key":"10.1016\/0166-218X(95)00103-X_BIB94","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1137\/0220026","article-title":"Fast matching algorithms for points on a polygon","volume":"20","author":"Marcotte","year":"1991","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(95)00103-X_BIB95","first-page":"531","article-title":"On a class of polynomially solvable travelling salesman problems","volume":"19","author":"Michalski","year":"1987","journal-title":"Zastosowania Mathematyki"},{"key":"10.1016\/0166-218X(95)00103-X_BIB96","series-title":"Histoire de l'Acad\u00e9mie Royale des Sciences, Ann\u00e9e M. DCCLXXXI, avec les M\u00e9moires de Math\u00e9matique et de Physique, pour la m\u00eame Ann\u00e9e","first-page":"666","article-title":"M\u00e9moire sur la th\u00e9orie des d\u00e9blais et des remblais","author":"Monge","year":"1781"},{"key":"10.1016\/0166-218X(95)00103-X_BIB97","first-page":"105","article-title":"A concise survey of efficiently solvable special cases of the permutation flow shop-problem","volume":"17","author":"Monma","year":"1983","journal-title":"RAIRO Recherche op\u00e9rationelle"},{"key":"10.1016\/0166-218X(95)00103-X_BIB98_1","article-title":"Distributions with given marginals subject to certain constraints","author":"Olkin","year":"1990"},{"key":"10.1016\/0166-218X(95)00103-X_BIB98_2","author":"Olkin","year":"1990"},{"key":"10.1016\/0166-218X(95)00103-X_BIB99","article-title":"Mass transportation problems with capacity constraints","author":"Olkin","year":"1991"},{"key":"10.1016\/0166-218X(95)00103-X_BIB100","series-title":"Proceedings of the 20th Annual ACM Symposium on the Theory of Computing","first-page":"377","article-title":"A faster strongly polynomial minimum cost flow algorithm","author":"Orlin","year":"1988"},{"key":"10.1016\/0166-218X(95)00103-X_BIB101","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1016\/0196-6774(86)90007-6","article-title":"An optimal algorithm for finding minimal enclosing triangles","volume":"7","author":"O'Rourke","year":"1986","journal-title":"J. Algorithms"},{"key":"10.1016\/0166-218X(95)00103-X_BIB102","article-title":"The Monge array: an abstraction and its applications","author":"Park","year":"1991"},{"key":"10.1016\/0166-218X(95)00103-X_BIB103","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0020-0190(91)90118-2","article-title":"A special case of the n-vertex traveling salesman problem that can be solved in O(n) time","volume":"40","author":"Park","year":"1991","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0166-218X(95)00103-X_BIB104","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/0167-6377(94)90037-X","article-title":"Monge matrices make maximization manageable","volume":"16","author":"Pferschy","year":"1994","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/0166-218X(95)00103-X_BIB105","series-title":"Proceedings of the Third IPCO Conference","first-page":"385","article-title":"A general class of greedily solvable linear programs","author":"Queyranne","year":"1993"},{"key":"10.1016\/0166-218X(95)00103-X_BIB106","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1137\/1129093","article-title":"The Monge-Kantorovich mass transference problem and its stochastic applications","volume":"29","author":"Rachev","year":"1984","journal-title":"Theory Probab. Appl."},{"key":"10.1016\/0166-218X(95)00103-X_BIB107","series-title":"Probability Metrics and the Stability of Stochastic Models","author":"Rachev","year":"1991"},{"key":"10.1016\/0166-218X(95)00103-X_BIB108","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1137\/S0363012991221365","article-title":"Solution of some transportation problems with relaxed or additional constraints","volume":"32","author":"Rachev","year":"1994","journal-title":"SIAM J. Control Optimi."},{"key":"10.1016\/0166-218X(95)00103-X_BIB109","first-page":"1453","article-title":"On the symmetric traveling salesman problem","volume":"32","author":"Rubinshtein","year":"1971","journal-title":"Automat. Remote Control"},{"key":"10.1016\/0166-218X(95)00103-X_BIB110","article-title":"Monge properties and their recognition","author":"Rudolf","year":"1993"},{"key":"10.1016\/0166-218X(95)00103-X_BIB111","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0166-218X(92)00189-S","article-title":"Recognition of d-dimensional Monge arrays","volume":"52","author":"Rudolf","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB112","doi-asserted-by":"crossref","DOI":"10.1016\/S0024-3795(97)00007-4","article-title":"On Monge sequences in d-dimensional arrays","author":"Rudolf","year":"1993"},{"key":"10.1016\/0166-218X(95)00103-X_BIB113","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF01415751","article-title":"The cone of Monge matrices: extremal rays and applications","volume":"42","author":"Rudolf","year":"1995","journal-title":"ZOR Methods Models Oper. Res."},{"key":"10.1016\/0166-218X(95)00103-X_BIB114","article-title":"On quadratic choice problems","author":"Sarvanov","year":"1978"},{"key":"10.1016\/0166-218X(95)00103-X_BIB115","series-title":"Proceedings of the Sixth ACM-SIAM Symposium on Algorithms","first-page":"405","article-title":"Computing a minimum-weight k-link path in graphs with the concave Monge property","author":"Schieber","year":"1995"},{"key":"10.1016\/0166-218X(95)00103-X_BIB116","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1016\/0012-365X(93)90382-4","article-title":"A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs","volume":"114","author":"Shamir","year":"1993","journal-title":"Discrete Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB117","series-title":"Proceedings of the First ACM-SIAM Symposium of Discrete Algorithms","first-page":"358","article-title":"Characterization and algorithms for greedily solvable transportation problems","author":"Shamir","year":"1990"},{"key":"10.1016\/0166-218X(95)00103-X_BIB118","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","article-title":"Bipartite permutation graphs","volume":"18","author":"Spinrad","year":"1987","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB119","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1137\/S0895480191197210","article-title":"Nonredundant Is in \u0393-free matrices","volume":"8","author":"Spinrad","year":"1995","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB120","doi-asserted-by":"crossref","first-page":"179","DOI":"10.2307\/1970124","article-title":"Extreme hamiltonian lines","volume":"66","author":"Supnick","year":"1957","journal-title":"Ann. Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB121","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0167-6377(93)90091-T","article-title":"An instant solution of the 2 \u00d7 n bottleneck transportation problem","volume":"14","author":"Szwarc","year":"1993","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/0166-218X(95)00103-X_BIB122","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1214\/aop\/1176994668","article-title":"Inequalities for distributions with given marginals","volume":"8","author":"Tchen","year":"1980","journal-title":"The Ann. Probab."},{"key":"10.1016\/0166-218X(95)00103-X_BIB123","series-title":"Proceedings of the 34-th Annual IEEE Symposium on Foundations of Computer Science","first-page":"158","article-title":"Approximating shortest superstrings","author":"Teng","year":"1993"},{"key":"10.1016\/0166-218X(95)00103-X_BIB124","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1287\/opre.26.2.305","article-title":"Minimizing a submodular function on a lattice","volume":"26","author":"Topkis","year":"1978","journal-title":"Oper. Res."},{"issue":"B","key":"10.1016\/0166-218X(95)00103-X_BIB125","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0095-8956(72)90019-6","article-title":"A structure theorem for the consecutive ones property","volume":"12","author":"Tucker","year":"1972","journal-title":"J. Combina. Theory"},{"key":"10.1016\/0166-218X(95)00103-X_BIB126","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1016\/0167-6377(91)90072-W","article-title":"An optimal algorithm for 2 \u00d7 n bottleneck transportation problems","volume":"10","author":"Varadarajan","year":"1991","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/0166-218X(95)00103-X_BIB127","article-title":"Solvable cases of the traveling salesman problem with various objective functions","author":"van der Veen","year":"1992"},{"key":"10.1016\/0166-218X(95)00103-X_BIB128","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0166-218X(93)90152-E","article-title":"An O(n) algorithm to solve the bottleneck traveling salesman problem restricted to ordered product matrices","volume":"47","author":"van der Veen","year":"1993","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB129","article-title":"Unpublished class notes","author":"Veinott","year":"1963"},{"key":"10.1016\/0166-218X(95)00103-X_BIB130","doi-asserted-by":"crossref","first-page":"S145","DOI":"10.1287\/opre.40.1.S145","article-title":"Economic lot sizing: An O(n log n) algorithm that runs in linear time in the Wagner-Whitin case","volume":"40","author":"Wagelmans","year":"1992","journal-title":"Oper. Res."},{"key":"10.1016\/0166-218X(95)00103-X_BIB131","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1287\/mnsc.5.1.89","article-title":"Dynamic version of the economic lot size model","volume":"5","author":"Wagner","year":"1958","journal-title":"Management Sci."},{"key":"10.1016\/0166-218X(95)00103-X_BIB132","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1016\/0196-8858(86)90025-4","article-title":"Rapid dynamic programming algorithms for RNA secondary structure","volume":"7","author":"Waterman","year":"1986","journal-title":"Advances Appl. Math."},{"key":"10.1016\/0166-218X(95)00103-X_BIB133","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1016\/0196-6774(88)90032-6","article-title":"The concave least-weight subsequence problem revisited","volume":"9","author":"Wilber","year":"1988","journal-title":"J. Algorithms"},{"key":"10.1016\/0166-218X(95)00103-X_BIB134","series-title":"Personal communication","author":"Woeginger","year":"1994"},{"key":"10.1016\/0166-218X(95)00103-X_BIB135","series-title":"Proceedings of the 12-th Annual ACM Symposium on Theory of Computing","first-page":"429","article-title":"Efficient dynamic programming using quadrangle inequalities","author":"Yao","year":"1980"},{"key":"10.1016\/0166-218X(95)00103-X_BIB136","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1137\/0603055","article-title":"Speed-up in dynamic programming","volume":"3","author":"Yao","year":"1982","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10.1016\/0166-218X(95)00103-X_BIB137","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1287\/mnsc.13.1.105","article-title":"A deterministic multi-period production scheduling model with backlogging","volume":"13","author":"Zangwill","year":"1966","journal-title":"Management Sci."},{"key":"10.1016\/0166-218X(95)00103-X_BIB138","article-title":"Linear and combinatorial optimization in ordered algebraic structures","volume":"10","author":"Zimmermann","year":"1981"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0166218X9500103X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0166218X9500103X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T18:27:43Z","timestamp":1556130463000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0166218X9500103X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,9]]},"references-count":142,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1996,9]]}},"alternative-id":["0166218X9500103X"],"URL":"https:\/\/doi.org\/10.1016\/0166-218x(95)00103-x","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[1996,9]]}}}