Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
Volume 28, No 3, 2021, P. 5-37
UDC 519.8
O. I. Duginov
A weighted perfect matching with constraints on weights of its parts
Abstract:
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 edgeweighted bipartite graph.
Illustr. 5, bibliogr. 29.
Keywords: perfect matching, assignment problem, NP-hardness.
DOI: 10.33048/daio.2021.28.667
Oleg I. Duginov 1
e-mail: duginov@bsu.by
Received July 15, 2019
Revised April 28, 2021
Accepted April 30, 2021
References
[1] G. Monge, Mémoire sur la théorie des déblais et de remblais, Histoire de l’Académie Royale des Sciences de Paris, 666–704 (1781) [French].[2] A. Schrijver, On the history of combinatorial optimization (till 1960), Handb. Oper. Res. Manag. Sci. 12, 1–68 (2005).
[3] R. Burkard, M. Dell’Amico, and S. Martello, Assignment Problems (SIAM, Philadelphia, PA, 2009).
[4] D. W. Pentico, Assignment problems: A golden anniversary survey, Eur. J. Oper. Res. 176, 774–793 (2007).
[5] D. R. Fulkerson, I. Glicksberg, and O. Gross, A production line assignment problem, Tech. Rep. RM-1102 (The Rand Corp., Santa Monica, CA, 1953).
[6] T. C. Koopmans and M. J. Beckmann, Assignment problems and the location of economic activities, Econometrica 25, 53–76 (1957).
[7] V. M. Demidenko, Quadratic assignment problems with additively monotone matrices and incomplete anti-Monge matrices: Conditions for effective solvability, Diskretn. Mat. 19, 105–132 (2007) [Russian] [Discrete Math. Appl. 12, 105–133 (2007)].
[8] S. Martello, W. R. Pulleyblank, P. Toth, and D. de Werra, Balanced optimization problems, Oper. Res. Lett. 3, 275–278 (1984).
[9] M. Barketau, E. Pesch, and Ya. Shafransky, Minimizing maximum weight of subsets of a maximum matching in a bipartite graph, Discrete Appl. Math. 196, 4–19 (2015).
[10] D. Kress, S. Meiswinkel, and E. Pesch, The partitioning min-max weighted matching problem, Eur. J. Oper. Res. 247, 745–754 (2015).
[11] X. Li, A. Otto, and E. Pesch, Solving the single crane scheduling problem at rail transshipment yards, Discrete Appl. Math. 264, 134–147 (2019).
[12] S. Meiswinkel, On Combinatorial Optimization and Mechanism Design Problems Arising at Container Ports (Springer Gabler, Wiesbaden, 2018).
[13] E. Pesch and K. Kuzmicz, Non-approximability of the single crane container transshipment problem, Int. J. Prod. Res. 58, 3965–3975 (2020).
[14] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, and R. I. Tyshkevich, Lectures on Graph Theory (Nauka, Moscow, 1990 [Russian]; B. I. Wissenschaftsverlag, Mannheim, 1994).
[15] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]).
[16] R. Gurjar, A. Korwar, J. Messner, S. Straub, and T. Thierauf, Planarizing gadgets for perfect matching do not exist, in Mathematical Foundations of Computer Science 2012 (Proc. 37th Int. Symp., Bratislava, Slovakia, Aug. 27–31, 2012) (Springer, Heidelberg, 2012), pp. 478–490 (Lect. Notes Comput.
Sci., Vol. 7464).
[17] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Upper Saddle River, NJ, 1993).
[18] B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms (Springer, Heidelberg, 2012; MTsNMO, Moscow, 2015 [Russian]) (Algorithms Comb., Vol. 21).
[19] K. Cameron, Coloured matchings in bipartite graphs, Discrete Math. 169, 205–209 (1997).
[20] A. Itai and M. Rodeh, Finding a minimum circuit in a graph, in Proc. 9th Annu. ACM Symp. Theory of Computing, Boulder, CO, USA, May 2–4, 1977 (ACM, New York, 1977), pp. 1–10.
[21] A. Itai, M. Rodeh, and S. L. Tanimoto, Some matching problems for bipartite graphs, J. ACM 25 (4), 517–525 (1978).
[22] C. H. Papadimitriou and M. Yannakakis, The complexity of restricted spanning tree problems, J. ACM 29 (2), 285–309 (1982).
[23] A. V. Karzanov, Maximum matching of given weight in complete and complete bipartite graphs, Kibernetika, No. 1, 7–11 (1987) [Russian] [Cybern. Syst. Anal. 23, 8–13 (1987)].
[24] G. Zhu, X. Luo, and Y. Miao, Exact weight perfect matching of bipartite graph is NP-complete, in Proc. World Congr. Engineering 2008, London, UK, July 2–4, 2008, Vol. II (Newswood, London, 2008),
[25] R. Gurjar, A. Korwar, J. Messner, and T. Thierauf, Exact perfect matching in complete graphs, ACM Trans. Comput. Theory 9 (2), 8:1–8:20 (2017).
[26] M. Milanic and J. Monnot, The exact weighted independent set problem in perfect graphs and related classes, Electron. Notes Discrete Math. 35, 317–322 (2009).
[27] H. N. Gabow and R. E. Tarjan, Faster scaling algorithms for network problems, SIAM J. Comput. 18, 1013–1036 (1989).
[28] L. Ramshaw and R. E. Tarjan, A weight-scaling algorithm for min-cost imperfect matchings in bipartite graphs, in Proc. 53rd Annu. Symp. Foundations of Computer Science, New Brunswick, NJ, USA, Oct. 20–23, 2012 (IEEE, Piscataway, 2012), pp. 581–590.
[29] H. N. Gabow and R. E. Tarjan, Faster scaling algorithms for general graph matching problems, J. ACM 38 (4), 815–853 (1991).
