EN|RU
|
![]() |
Volume 28, No 3, 2021, P. 5-37 UDC 519.8
Keywords: perfect matching, assignment problem, NP-hardness. DOI: 10.33048/daio.2021.28.667 Oleg I. Duginov 1 Received July 15, 2019 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). |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|