×

Weak Monge arrays in higher dimensions. (English) Zbl 0958.05017

Summary: An \(n\times n\) matrix \(C\) is called a weak Monge matrix if \(c_{ii}+ c_{rs}\leq c_{is}+ c_{ri}\) for all \(1\leq i\leq r, s\leq n\). It is well known that the classical linear assignment problem is optimally solved by the identity permutation if the underlying cost-matrix fulfills the weak Monge property.
In this paper we introduce \(d\)-dimensional weak Monge arrays, \((d\geq 2)\), and prove that \(d\)-dimensional axial assignment problems can be solved efficiently whenever the underlying cost-array fulfills the \(d\)-dimensional weak Monge property. Moreover, it is shown that all results also carry over into an abstract algebraic framework. Finally, the problem of testing whether or not a given array can be permuted to become a weak Monge array is investigated.

MSC:

05B30 Other designs, configurations
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Cosares, S.; Hochbaum, D. S.; Shamir, R., An algorithm for the detection and construction of Monge sequences, Linear Algeb. Appl., 114/115, 669-680 (1989) · Zbl 0666.65044
[2] Aggarwal, A.; Park, J. K., Notes on searching in multidimensional monotone arrays, (Proc. 29th Ann. IEEE Symp. on Foundations of Computer Science (1988)), 497-512
[3] Bein, 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
[4] Burkard, R. E.; Klinz, B.; Rudolf, R., Perspectives of Monge properties in optimization, Discrete Appl. Math., 70, 95-161 (1996) · Zbl 0856.90091
[5] Cechlárová, K.; Szabó, P., On the Monge property of matrices, Discrete Math., 81, 123-128 (1990) · Zbl 0726.06010
[6] Derigs, U.; Goecke, O.; Schrader, R., Monge sequences and a simple assignment algorithm, Discrete Appl. Math., 15, 241-248 (1986) · Zbl 0646.90068
[7] Hoffman, A. J., On simple linear programming problems, (Klee, V., Proc. Symp. in Pure Mathematics. Proc. Symp. in Pure Mathematics, Convexity, vol. VII (1961), AMS: AMS Providence, RI), 317-327
[8] Monge, G., Mémoire sur la théorie des déblais et des remblais, Histoire de l’Académie Royale des Sciences, (Année MDCCLXXXI, avec les Mémoires de Mathématique et de Physique, pour la meme Année (1781), Tirés des Registres de cette Académie: Tirés des Registres de cette Académie Paris), 666-704
[9] Rudolf, R., On Monge sequences in \(d\)-dimensional arrays, Linear Algeb. Appl., 268, 59-70 (1998) · Zbl 0889.90113
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.