×

zbMATH — the first resource for mathematics

Perspectives of Monge properties in optimization. (English) Zbl 0856.90091
Summary: An \(m\times n\) matrix \(C\) is called Monge matrix if \(c_{ij}+ c_{rs}\leq c_{is}+ c_{rj}\) for all \(1\leq i< r\leq m\), \(1\leq j< s\leq n\). We present a survey on Monge matrices and related Monge properties and their role in combinatorial optimization. Specifically, we deal with the following three main topics: (i) fundamental combinatorial properties of Monge structures, (ii) applications of Monge properties to optimization problems and (iii) recognition of Monge properties.

MSC:
90C27 Combinatorial optimization
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adler, I.; Hoffman, A.J.; Shamir, R., Monge and feasibility sequences in general flow problems, Discrete appl. math., 44, 21-38, (1993) · Zbl 0780.90028
[2] Adler, I.; Shamir, R., Greedily solvable transportation networks and edge-guided vertex elimination, (), 1-22
[3] Aggarwal, A.; Bar-Noy, A.; Khuller, S.; Kravets, D.; Schieber, B., Efficient minimum cost matching using quadrangle inequality, (), 583-592 · Zbl 0942.68778
[4] Aggarwal, A.; Klawe, M.M.; Moran, S.; Shor, P.; Wilber, R., Geometric applications of a matrix-searching algorithm, Algorithmica, 2, 195-208, (1987) · Zbl 0642.68078
[5] Aggarwal, A.; Park, J.K., Notes on searching in multidimensional monotone arrays, (), 497-512
[6] Aggarwal, A.; Park, J.K., Sequential searching in multidimensional monotone arrays, (), portions of this paper appeared in [5]
[7] Aggarwal, A.; Park, J.K., Parallel searching in multidimensional monotone arrays, (), portions of this paper appeared in [5] · Zbl 0895.68028
[8] Aggarwal, A.; Park, J.K., Improved algorithms for economic lot-size problems, Oper. res., 41, 549-571, (1993) · Zbl 0820.90035
[9] Aggarwal, A.; Park, J.K., More applications of Monge-array techniques to economic lot-size problems, (1993), unpublished manuscript
[10] Aggarwal, A.; Schieber, B.; Tokuyama, T., Finding a minimum weight K-link path in graphs with Monge property and applications, Discrete comput. geometry, 12, 263-280, (1994) · Zbl 0819.68084
[11] Agarwal, P.K.; Sen, S., Selection in monotone matrices and kth nearest neighbors, (), 13-24
[12] Aizenshtat, V.S.; Kravchuk, D.N., Algorithms for finding extremum of a linear form on the set of all cycles in special cases, Dokl. akad. nauk BSSR, 12, 401-404, (1968), (in Russian) · Zbl 0172.01301
[13] Aizenshtat, V.S.; Maksimovich, E.P.; Aizenshtat, V.S.; Maksimovich, E.P., Special cases of traveling salesman problems, Kibernetika, Cybernetics, 14, 565-569, (1979), (English translation) · Zbl 0415.90056
[14] Alon, N.; Cosares, S.; Hochbaum, D.S.; Shamir, R., An algorithm for the detection and construction of Monge sequences, Linear algebra appl., 114/115, 669-680, (1989) · Zbl 0666.65044
[15] Anderson, E.J.; Nash, P., Linear programming in infinite-dimensional spaces: theory and applications, () · Zbl 0632.90038
[16] Apostolico, A.; Atallah, M.J.; Larmore, L.L.; McFaddin, H.S., Efficient parallel algorithms for string editing and related problems, SIAM J. comput., 19, 968-988, (1990) · Zbl 0711.68055
[17] Balinski, M.L.; Rachev, S.T., On Monge-Kantorovich problems, (1989), SUNY at Stony Brook, Department of Applied Mathematics and Statistics, preprint
[18] Barnes, E.R.; Hoffman, A.J., On transportation problems with upper bounds on leading rectangles, SIAM J. algebraic discrete methods, 6, 487-496, (1985) · Zbl 0589.90056
[19] Bein, W.W.; Brucker, P.; Hoffman, A.J., Series parallel composition of greedy linear programming problems, Math. programming, 62, 1-14, (1993) · Zbl 0801.90076
[20] Bein, W.W.; Brucker, P.; Park, J.K., Applications of an algebraic Monge property, (), unpublished manuscript
[21] Bein, W.W.; Brucker, P.; Park, J.K.; Pathak, P.K., A Monge property for the d-dimensional transportation problem, Discrete appl. math., 58, 97-109, (1995) · Zbl 0833.90083
[22] Bein, W.W.; Brucker, P.; Tamir, A., Minimum cost flow algorithms for series-parallel networks, Discrete appl. math., 10, 117-124, (1985) · Zbl 0571.90019
[23] Bein, W.; Pathak, P.K., A characterization of the Monge property, () · Zbl 1006.91503
[24] Blum, A.; Jiang, T.; Li, M.; Tromp, J.; Yannakakis, M., Linear approximation of shortest superstrings, (), 328-336
[25] Borchers, A.; Gupta, P., Extending the quadrangle inequality to speed-up dynamic programming, Inform. process. lett., 49, 287-290, (1994) · Zbl 0801.90122
[26] Burdyuk, V.Y.; Trofimov, V.N.; Burdyuk, V.Y.; Trofimov, V.N., Generalization of the results of gilmore and Gomory on the solution of the traveling salesman problem, Izw. akad. nauk SSSR tech. kibernet, Engi. cybernet., 14, 12-18, (1976), (English translation)
[27] Burkard, R.E., Remarks on some scheduling problems with algebraic objective function, Methods oper. res., 32, 63-77, (1978) · Zbl 0405.90035
[28] Burkard, R.E., A general Hungarian method for the algebraic transportation problem, Discrete math., 22, 219-232, (1978) · Zbl 0373.90047
[29] Burkard, R.E., Assignment problems: recent solution methods and applications, (), 153-169
[30] Burkard, R.E., Special cases of travelling salesman problems and heuristics, Acta math. appl. sinica, 6, 273-288, (1990) · Zbl 0718.90027
[31] Burkard, R.E., On the role of bottleneck Monge matrices in combinatorial optimization, Oper. res. lett., 17, 53-56, (1995) · Zbl 0836.90127
[32] Burkard, R.E.; Çela, E.; Demidenko, V.M.; Metelski, N.N.; Woeginger, G.J., Easy and hard cases of the quadratic assignment problem: a survey, manuscript, ()
[33] Burkard, R.E.; Çela, E.; Rote, G.; Woeginger, G.J., The quadratic assignment problem with an anti-Monge and a Toeplitz matrix: easy and hard cases, (), Mathematical Programming, to appear · Zbl 0949.90077
[34] Burkard, R.E.; Deǐneko, V.G., Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood, Computing, 54, 191-211, (1995) · Zbl 0821.90122
[35] Burkard, R.E.; Deǐneko, V.G.; van Dal, R.; van der Veen, J.A.A.; Woeginger, G.J., Well-solvable special cases of the TSP: A survey, () · Zbl 1052.90597
[36] Burkard, R.E.; Deǐneko, V.G.; Woeginger, G.J., The traveling salesman problem on permuted Monge matrices, (), submitted · Zbl 0955.90113
[37] Burkard, R.E.; Rudolf, R.; Woeginger, G.J., Axial assignment problems with decomposable cost coefficients, (), Discrete Appl. Math., to appear · Zbl 0846.90090
[38] Burkard, R.E.; Sandholzer, W., Efficiently solvable special cases of bottleneck travelling salesman problems, Discrete appl. math., 32, 61-76, (1991) · Zbl 0747.90081
[39] Burkard, R.E.; van der Veen, J.A.A., Universal conditions for algebraic travelling salesman problems to be efficiently solvable, Optimization, 22, 787-814, (1991) · Zbl 0732.90088
[40] Burkard, R.E.; Zimmermann, U., Weakly admissible transformations for solving algebraic assignment and transportation problems, Math. programming study, 12, 1-18, (1980) · Zbl 0435.90108
[41] Buss, S.R.; Yianilos, P.N., Linear and O(n log n) time minimum-cost matching algorithms for quasi-convex tours, (), 65-76 · Zbl 0867.05071
[42] Cambanis, S.; Simons, G.; Stout, W., Inequalities for ek(X, Y) when the marginals are fixed, Zeitschrift für wahrscheinlichkeitstheorie und verwandte gebiete, 36, 285-294, (1976) · Zbl 0325.60002
[43] Cechlárová, K.; Szabó, P., On the Monge property of matrices, Discrete math., 81, 123-128, (1990) · Zbl 0726.06010
[44] Çela, E., The quadratic assignment problem: special cases and relatives, ()
[45] Chen, L.; Yesha, Y., Efficient parallel algorithms for bipartite permutation graphs, Networks, 22, 29-39, (1993) · Zbl 0795.90078
[46] Deǐneko, V.G., Applying dynamic programming to solving a special multi-traveling salesmen problem, (), 47-50, (in Russian)
[47] Deǐneko, V.G.; Filonenko, V.L., On the reconstruction of specially structured matrices, (), (in Russian)
[48] Deǐneko, V.G.; Rudolf, R.; van der Veen, J.A.A.; Woeginger, G.J., Three easy special cases of the Euclidean travelling salesman problem, (), submitted for publication · Zbl 0888.90141
[49] Deǐneko, V.G.; Rudolf, R.; Woeginger, G.J., The recognition of permuted supnik and incomplete Monge matrices, (), Acta Inform., to appear · Zbl 0858.68042
[50] Deǐneko, V.G.; Rudolf, R.; Woeginger, G.J.; Deǐneko, V.G.; Rudolf, R.; Woeginger, G.J., An extended abstract appeared, (), 128-141, submitted for publication
[51] Demidenko, V.M., A special case of travelling salesman problems, Izv. akad. nauk. BSSR, ser. fiz.-mat. nauk, 5, 28-32, (1976), (in Russian) · Zbl 0366.90090
[52] Derigs, U.; Goecke, O.; Schrader, R., Bisimplicial edges, Gaussian elimination and matchings in bipartite graphs, (), 79-87
[53] Derigs, U.; Goecke, O.; Schrader, R., Monge sequences and a simple assignment algorithm, Discrete appl. math., 15, 241-248, (1986) · Zbl 0646.90068
[54] Dietrich, B.L., Monge sequences, antimatroids and the transportation problem with forbidden arcs, Linear algebra appl., 139, 133-145, (1990) · Zbl 0703.90063
[55] Eiselt, H.A.; Burkard, R.E., Reshipments and overshipments in transportation problems with minimax objective, OR spektrum, 13, 133-140, (1991) · Zbl 0751.90049
[56] Eppstein, D., Sequence comparison with mixed convex and concave costs, J. algorithms, 11, 85-101, (1990) · Zbl 0709.68015
[57] Erickson, R.E.; Monma, C.L.; Veinott, A.F., Send-and-split method for minimum-concave-cost network flows, Math. oper. res., 12, 634-664, (1987) · Zbl 0667.90036
[58] Faigle, U., Some recent results in the analysis of greedy algorithms for assignment problems, OR spektrum, 15, 181-188, (1994) · Zbl 0797.90068
[59] Faigle, U.; Kern, W., Submodular linear programs on forests, (), Math. Programming, to appear · Zbl 0856.90071
[60] Federgruen, A.; Tzur, M., A simple forward algorithm to solve general dynamic lot sizing models with n periods in O(nlogn) or O(n) time, Management sci., 37, 909-925, (1991) · Zbl 0748.90011
[61] Fortin, D.; Rudolf, R., Weak algebraic Monge arrays, (), submitted for publication
[62] Frechét, M., Sur LES tableaux de corrélation dont LES marges sont données, Annales de l’université de Lyon, section A, 14, 53-77, (1951) · Zbl 0045.22905
[63] Frechét, M., Sur LES tableaux de corrélation dont LES marges sont données, Annales de l’université de Lyon, section A, 20, 13-31, (1957)
[64] Gaikov, N.E., On the minimization of a linear form on cycles, Vestsi akad. navuk BSSR ser. fiz.-mat. navuk, 4, 128, (1980), (in Russian)
[65] Galil, Z.; Park, K., A linear-time algorithm for concave one-dimensional dynamic programming, Inform. process. lett., 33, 309-311, (1990) · Zbl 0694.68032
[66] Gilmore, P.C.; Lawler, E.L.; Shmoys, D.B., Well-solved special cases, (), 87-143, Chap. 4 · Zbl 0631.90081
[67] Girlich, E.; Kovalev, M.M.; Zaporozhets, A.A., Subcones of submodular functions (subclasses of Monge matrices), () · Zbl 1052.90632
[68] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[69] Golumbic, M.C.; goss, C.F., Perfect elimination and chordal bipartite graphs, J. graph theory, 2, 155-163, (1978) · Zbl 0411.05060
[70] Graves, S.C.; Orlin, J.B., A minimum concave-cost dynamic network flow problem with an application to lot-sizing, Networks, 15, 59-71, (1985) · Zbl 0579.90032
[71] Gusfield, D., Design (with analysis) of efficient algorithms, (), 375-453, Computing, Chap. 8 North-Holland · Zbl 0782.68056
[72] Hardy, G.H.; Littlewood, J.E.; Pólya, G., Inequalities, (1952), Cambridge Univ. Press Cambridge · Zbl 0047.05302
[73] Hirschberg, D.S.; Larmore, L.L., The least weight subsequence problem, SIAM J. comput., 16, 628-638, (1987) · Zbl 0651.68092
[74] Hoeffding, W., Maβstabsinvariante korrelationstheorie, Schriften des mathematischen instituts und des instituts für angewandte Mathematik der universität Berlin, 5, 179-233, (1940)
[75] Hoffman, A.J., On simple linear programming problems, (), 317-327
[76] Hoffman, A.J., On greedy algorithms that succeed, (), 97-112 · Zbl 0601.90111
[77] Hoffman, A.J., On greedy algorithms for series parallel graphs, Math. programming, 40, 197-204, (1988) · Zbl 0652.90040
[78] Hoffman, A.J.; Veinott, A.F., Staircase transportation problems with superadditive rewards and cumulative capacities, Math. programming, 62, 199-213, (1993) · Zbl 0799.90091
[79] Johnson, S.M., Optimal two and three-stage production schedules with setup times included, Naval res. logistics quart., 1, 61-68, (1954) · Zbl 1349.90359
[80] Kalmanson, K., Edgeconvex circuits and the traveling salesman problem, Can. J. math., 27, 1000-1010, (1975) · Zbl 0284.05117
[81] Kantorovich, L.V., On the transfer of masses, Doklady akad. nauk. USSR, 37, 227-229, (1942)
[82] Kantorovich, L.V., On a problem of Monge, Uspekhi mat. nauk., 3, 225-226, (1948), (in Russian)
[83] Karlin, S., ()
[84] Karp, R.M.; Li, S-Y.R., Two special cases of the assignment problem, Discrete math., 13, 129-142, (1975) · Zbl 0311.90066
[85] Klawe, M.M.; Kleitman, D.J., An almost linear time algorithm for generalized matrix searching, SIAM J. discrete math., 3, 81-97, (1990) · Zbl 0689.68062
[86] Klinz, B.; Rudolf, R.; Woeginger, G.J., Permuting matrices to avoid forbidden submatrices, Discrete appl. math., 60, 223-248, (1995) · Zbl 0837.05031
[87] Klinz, B.; Rudolf, R.; Woeginger, G.J., On the recognition of permuted bottleneck Monge matrices, Discrete appl. math., 63, 43-74, (1995) · Zbl 0840.05058
[88] Korte, B.; Lovász, L.; Schrader, R., Greedoids, (1991), Springer Berlin · Zbl 0733.05023
[89] Kravets, D.; Park, J.K., Selection and sorting in totally monotone matrices, Math. systems theory, 24, 201-220, (1991) · Zbl 0766.68022
[90] Larmore, L.L.; Schieber, B., On-line dynamic programming with applications to the prediction of RNA secondary structure, J. algorithms, 12, 490-515, (1991) · Zbl 0724.90080
[91] Lorentz, G.G., An inequality for rearrangements, Amer. math. monthly, 60, 176-179, (1953) · Zbl 0050.28201
[92] Lovász, L., Submodular functions and convexity, (), 235-257
[93] Mansour, Y.; Park, J.K.; Schieber, B.; Sen, S., Improved selection in totally monotone arrays, Int. J. comput. geometry appl., 3, 115-132, (1993) · Zbl 0777.68033
[94] Marcotte, O.; Suri, S., Fast matching algorithms for points on a polygon, SIAM J. comput., 20, 405-422, (1991) · Zbl 0743.68133
[95] Michalski, M., On a class of polynomially solvable travelling salesman problems, Zastosowania mathematyki, 19, 531-539, (1987) · Zbl 0721.90074
[96] Monge, G., Mémoire sur la théorie des déblais et des remblais, (), 666-704
[97] Monma, C.L.; Kan, A.H.G.Rinnooy, A concise survey of efficiently solvable special cases of the permutation flow shop-problem, RAIRO recherche opérationelle, 17, 105-119, (1983) · Zbl 0523.90054
[98] Olkin, I.; Rachev, S.T.; Olkin, I.; Rachev, S.T., Distributions with given marginals subject to certain constraints, () · Zbl 0946.60009
[99] Olkin, I.; Rachev, S.T., Mass transportation problems with capacity constraints, () · Zbl 0946.60009
[100] Orlin, J.B., A faster strongly polynomial minimum cost flow algorithm, (), 377-387
[101] O’Rourke, J.; Aggarwal, A.; Maddila, S.; Baldwin, M., An optimal algorithm for finding minimal enclosing triangles, J. algorithms, 7, 258-268, (1986) · Zbl 0606.68038
[102] Park, J.K., The Monge array: an abstraction and its applications, ()
[103] Park, J.K., A special case of the n-vertex traveling salesman problem that can be solved in O(n) time, Inform. process. lett., 40, 247-254, (1991) · Zbl 0743.68079
[104] Pferschy, U.; Rudolf, R.; Woeginger, G.J., Monge matrices make maximization manageable, Oper. res. lett., 16, 245-254, (1994) · Zbl 0822.90112
[105] Queyranne, M.; Spieksma, F.; Tardella, F., A general class of greedily solvable linear programs, (), 385-399 · Zbl 0924.90107
[106] Rachev, S.T., The Monge-Kantorovich mass transference problem and its stochastic applications, Theory probab. appl., 29, 647-667, (1984), (translated from Teoriya Veroyatnostei i ee Primeneniya) · Zbl 0581.60010
[107] Rachev, S.T., Probability metrics and the stability of stochastic models, (1991), Wiley Chichester · Zbl 0725.60002
[108] Rachev, S.T.; Rüschendorf, L., Solution of some transportation problems with relaxed or additional constraints, SIAM J. control optimi., 32, 673-689, (1994) · Zbl 0797.60019
[109] Rubinshtein, M.I., On the symmetric traveling salesman problem, Automat. remote control, 32, 1453-1460, (1971), (translated from Avtomatika i Telemekhanika) · Zbl 0234.90043
[110] Rudolf, R., Monge properties and their recognition, ()
[111] Rudolf, R., Recognition of d-dimensional Monge arrays, Discrete appl. math., 52, 71-82, (1994) · Zbl 0819.90060
[112] Rudolf, R., On Monge sequences in d-dimensional arrays, (), submitted for publication · Zbl 0889.90113
[113] Rudolf, R.; Woeginger, G.J., The cone of Monge matrices: extremal rays and applications, ZOR methods models oper. res., 42, 161-168, (1995) · Zbl 0843.90101
[114] Sarvanov, V.I., On quadratic choice problems, (), Minsk, (in Russian) · Zbl 0388.65018
[115] Schieber, B., Computing a minimum-weight k-link path in graphs with the concave Monge property, (), 405-411 · Zbl 0848.68073
[116] Shamir, R., A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs, Discrete math., 114, 435-444, (1993) · Zbl 0799.90093
[117] Shamir, R.; Dietrich, B.L., Characterization and algorithms for greedily solvable transportation problems, (), 358-366 · Zbl 0800.68479
[118] Spinrad, J.; Brandstädt, A.; Stewart, L., Bipartite permutation graphs, Discrete appl. math., 18, 279-292, (1987) · Zbl 0628.05055
[119] Spinrad, J., Nonredundant Is in γ-free matrices, SIAM J. discrete math., 8, 251-257, (1995) · Zbl 0837.05028
[120] Supnick, F., Extreme Hamiltonian lines, Ann. math., 66, 179-201, (1957) · Zbl 0078.16502
[121] Szwarc, W., An instant solution of the 2 × n bottleneck transportation problem, Oper. res. lett., 14, 261-264, (1993) · Zbl 0795.90044
[122] Tchen, A.H., Inequalities for distributions with given marginals, The ann. probab., 8, 814-827, (1980) · Zbl 0459.62010
[123] Teng, S.-H.; Yao, F., Approximating shortest superstrings, (), 158-165
[124] Topkis, D.M., Minimizing a submodular function on a lattice, Oper. res., 26, 305-321, (1978) · Zbl 0379.90089
[125] Tucker, A., A structure theorem for the consecutive ones property, J. combina. theory, 12, B, 153-162, (1972) · Zbl 0208.52402
[126] Varadarajan, R., An optimal algorithm for 2 × n bottleneck transportation problems, Oper. res. lett., 10, 525-529, (1991) · Zbl 0744.90064
[127] van der Veen, J.A.A., Solvable cases of the traveling salesman problem with various objective functions, () · Zbl 0732.90088
[128] van der Veen, J.A.A., An O(n) algorithm to solve the bottleneck traveling salesman problem restricted to ordered product matrices, Discrete appl. math., 47, 57-75, (1993) · Zbl 0801.90120
[129] Veinott, A.F., Unpublished class notes, ()
[130] Wagelmans, A.; van Hoesel, S.; Kolen, A., Economic lot sizing: an O(n log n) algorithm that runs in linear time in the wagner-whitin case, Oper. res., 40, S145-S156, (1992) · Zbl 0771.90031
[131] Wagner, H.M.; Whitin, T.M., Dynamic version of the economic lot size model, Management sci., 5, 89-96, (1958) · Zbl 0977.90500
[132] Waterman, M.S.; Smith, T.F., Rapid dynamic programming algorithms for RNA secondary structure, Advances appl. math., 7, 455-464, (1986) · Zbl 0607.92012
[133] Wilber, R., The concave least-weight subsequence problem revisited, J. algorithms, 9, 418-425, (1988) · Zbl 0651.68093
[134] Woeginger, G.J., Personal communication, (1994)
[135] Yao, F.F., Efficient dynamic programming using quadrangle inequalities, (), 429-435
[136] Yao, F.F., Speed-up in dynamic programming, SIAM J. algebraic discrete methods, 3, 532-540, (1982) · Zbl 0494.90082
[137] Zangwill, W.I., A deterministic multi-period production scheduling model with backlogging, Management sci., 13, 105-119, (1966) · Zbl 0143.22101
[138] Zimmermann, U., Linear and combinatorial optimization in ordered algebraic structures, () · Zbl 0466.90045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.