A weighted perfect matching with~constraints~on~weights of~its parts

O. I. Duginov

Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 3, pp. 5-37.

Résumé

We consider the following strongly NP-hard problem. Given an edge–weighted balanced complete bipartite graph with a partition of its part into non-empty and pairwise disjoint subsets, the problem is to find a perfect matching of this graph such that maximum sum of weights of edges from the matching incident to vertices of a subset of the partition is minimum. We present a characterization of solutions of a special case of this problem, in which weights of graph edges take values from the set $\{0, 1, \Delta\},$ where $\Delta$ is an integer that is greater than the number of edges of the unit weight and there is a perfect matching of the graph that consists of edges with weights $0$ and $1$. Besides, we identify polynomially solvable and strongly NP-hard special cases of this problem. Finally, we show that if the number of subsets forming the partition is fixed then the considered problem is equivalent to the problem of finding a perfect matching of a given weight in an edge-weighted bipartite graph. Illustr. 5, bibliogr. 29.

Détail

Keywords: perfect matching, assignment problem, NP-hardness.

Bibliographie

[1] Monge G., “Mémoire sur la théorie des déblais et de remblais”, Histoire de l'Académie Royale des Sciences de Paris, 1781, 666–704 (French)

[2] Schrijver A., “On the history of combinatorial optimization (till 1960)”, Handb. Oper. Res. Manag. Sci., 12, 2005, 1–68 | Zbl

[3] Burkard R., Dell'Amico M., Martello S., Assignment problems, SIAM, Philadelphia, PA, 2009, 382 pp. | Zbl

[4] Pentico D. W., “Assignment problems: A golden anniversary survey”, Eur. J. Oper. Res., 176 (2007), 774–793 | Zbl

[5] Fulkerson D. R., Glicksberg I., Gross O., A production line assignment problem, Tech. Rep. RM-1102, The Rand Corp., Santa Monica, CA, 1953

[6] Koopmans T. C., Beckmann M. J., “Assignment problems and the location of economic activities”, Econometrica, 25 (1957), 53–76 | Zbl

[7] V. M. Demidenko, “Quadratic assignment problems with additively monotone matrices and incomplete anti-Monge matrices: Conditions for effective solvability”, Discrete Math. Appl., 12 (2007), 105–133 | Zbl

[8] Martello S., Pulleyblank W. R., Toth P., de Werra D., “Balanced optimization problems”, Oper. Res. Lett., 3 (1984), 275–278 | Zbl

[9] Barketau M., Pesch E., Shafransky Ya., “Minimizing maximum weight of subsets of a maximum matching in a bipartite graph”, Discrete Appl. Math., 196 (2015), 4–19 | Zbl

[10] Kress D., Meiswinkel S., Pesch E., “The partitioning min-max weighted matching problem”, Eur. J. Oper. Res., 247 (2015), 745–754 | Zbl

[11] Li X., Otto A., Pesch E., “Solving the single crane scheduling problem at rail transshipment yards”, Discrete Appl. Math., 264 (2019), 134–147 | Zbl

[12] Meiswinkel S., On combinatorial optimization and mechanism design problems arising at container ports, Springer Gabler, Wiesbaden, 2018, 123 pp. | Zbl

[13] Pesch E., Kuzmicz K., “Non-approximability of the single crane container transshipment problem”, Int. J. Prod. Res., 58 (2020), 3965–3975

[14] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich, Lectures on Graph Theory, B. I. Wissenschaftsverlag, Mannheim, 1994 | Zbl

[15] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | Zbl

[16] Gurjar R., Korwar A., Messner J., Straub S., Thierauf T., “Planarizing gadgets for perfect matching do not exist”, Mathematical Foundations of Computer Science 2012, Proc. 37th Int. Symp. (Bratislava, Slovakia, Aug. 27–31, 2012), Lect. Notes Comput. Sci., 7464, Springer, Heidelberg, 2012, 478–490 | Zbl

[17] Ahuja R. K., Magnanti T. L., Orlin J. B., Network flows: Theory, algorithms, and applications, Prentice-Hall, Upper Saddle River, NJ, 1993, 863 pp. | Zbl

[18] B. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms, Algorithms Comb., 21, Springer, Heidelberg, 2012 | Zbl

[19] Cameron K., “Coloured matchings in bipartite graphs”, Discrete Math., 169 (1997), 205–209 | Zbl

[20] Itai A., Rodeh M., “Finding a minimum circuit in a graph”, Proc. 9th Annu. ACM Symp. Theory of Computing (Boulder, CO, USA, May 2–4, 1977), ACM, New York, 1977, 1–10

[21] Itai A., Rodeh M., Tanimoto S. L., “Some matching problems for bipartite graphs”, J. ACM, 25:4 (1978), 517–525 | Zbl

[22] Papadimitriou C. H., Yannakakis M., “The complexity of restricted spanning tree problems”, J. ACM, 29:2 (1982), 285–309 | Zbl

[23] A. V. Karzanov, “Maximum matching of given weight in complete and complete bipartite graphs”, Cybern. Syst. Anal., 23 (1987), 8–13 | Zbl

[24] Zhu G., Luo X., Miao Y., “Exact weight perfect matching of bipartite graph is NP-complete”, Proc. World Congr. Engineering (London, UK, July 2–4, 2008), v. II, Newswood, London, 2008, 878–880

[25] Gurjar R., Korwar A., Messner J., Thierauf T., “Exact perfect matching in complete graphs”, ACM Trans. Comput. Theory, 9:2 (2017), 8:1–8:20

[26] Milanic M., Monnot J., “The exact weighted independent set problem in perfect graphs and related classes”, Electron. Notes Discrete Math., 35 (2009), 317–322 | Zbl

[27] Gabow H. N., Tarjan R. E., “Faster scaling algorithms for network problems”, SIAM J. Comput., 18 (1989), 1013–1036 | Zbl

[28] Ramshaw L., Tarjan R. E., “A weight-scaling algorithm for min-cost imperfect matchings in bipartite graphs”, Proc. 53rd Annu. Symp. Foundations of Computer Science (New Brunswick, NJ, USA, Oct. 20–23, 2012), IEEE, Piscataway, 2012, 581–590

[29] Gabow H. N., Tarjan R. E., “Faster scaling algorithms for general graph matching problems”, J. ACM, 38:4 (1991), 815–853 | Zbl