Том 28, номер 3, 2021 г., Стр. 5-37
УДК 519.8
Дугинов О. И.
Взвешенное совершенное паросочетание с ограничениями на суммарный вес его частей
Аннотация:
Рассматривается NP-трудная в сильном смысле задача поиска в сбалансированном полном двудольном графе с весами на рёбрах и разбиением одной его доли на несколько непустых непересекающихся множеств такого совершенного паросочетания, что наибольший суммарный вес рёбер паросочетания, покрывающих все вершины одного множества разбиения, минимален. Предложена характеризация решений специального случая этой задачи, в котором, во-первых, веса рёбер графа принимают значения из множества {0, 1, $\Delta$}, где $\Delta$ — целое число, большее количества рёбер единичного веса, и, во-вторых, есть совершенное паросочетание, состоящее исключительно из рёбер нулевого и единичного весов. Кроме этого, выделены полиномиально разрешимый и сильно NP-трудный случаи рассматриваемой задачи. Установлена эквивалентность специального случая задачи с фиксированным числом множеств, на которые разбивается доля графа, задаче поиска совершенного паросочетания заданного веса в сбалансированном двудольном графе с весами на рёбрах.
Ил. 5, библиогр. 29.
Ключевые слова: совершенное паросочетание, задача о назначениях, NP-трудность.
DOI: 10.33048/daio.2021.28.667
Дугинов Олег Иванович 1
1. Белорусский гос. университет
пр. Независимости, 4, 220030 Минск, Беларусь
Belarusian State University
4 Nezavisimosti Avenue, 220030 Minsk, Belarus
е-mail: duginov@bsu.by
Статья поступила 15 июля 2019 г.
После доработки — 28 апреля 2021 г.
Принята к публикации 30 апреля 2021 г.
Литература
[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. P. 666–704. [French].
[2] Schrijver A. On the history of combinatorial optimization (till 1960) // Handb. Oper. Res. Manag. Sci. 2005. Vol. 12. P. 1–68.
[3] Burkard R., Dell’Amico M., Martello S. Assignment problems. Philadelphia, PA: SIAM, 2009. 382 p.
[4] Pentico D. W. Assignment problems: A golden anniversary survey // Eur. J. Oper. Res. 2007. Vol. 176.
[5] Fulkerson D. R., Glicksberg I., Gross O. A production line assignment problem // Tech. Rep. RM-1102. Santa Monica, CA: The Rand Corp., 1953.
[6] Koopmans T. C., Beckmann M. J. Assignment problems and the location of economic activities // Econometrica. 1957. Vol. 25. P. 53–76.
[7] Демиденко В. М. Квадратичная задача о назначениях с аддитивно монотонными матрицами и неполными матрицами анти-Монжа: условия эффективной разрешимости // Дискрет. математика. 2007. Т. 19. С. 105–132.
[8] Martello S., Pulleyblank W. R., Toth P., de Werra D. Balanced optimization problems // Oper. Res. Lett. 1984. Vol. 3. P. 275–278.
[9] Barketau M., Pesch E., Shafransky Ya. Minimizing maximum weight of subsets of a maximum matching in a bipartite graph // Discrete Appl. Math. 2015. Vol. 196. P. 4–19.
[10] Kress D., Meiswinkel S., Pesch E. The partitioning min-max weighted matching problem // Eur. J. Oper. Res. 2015. Vol. 247. P. 745–754.
[11] Li X., Otto A., Pesch E. Solving the single crane scheduling problem at rail transshipment yards // Discrete Appl. Math. 2019. Vol. 264. P. 134–147.
[12] Meiswinkel S. On combinatorial optimization and mechanism design problems arising at container ports. Wiesbaden: Springer Gabler, 2018. 123 p.
[13] Pesch E., Kuzmicz K. Non-approximability of the single crane container transshipment problem // Int. J. Prod. Res. 2020. Vol. 58. P. 3965–3975
[14] Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384 с.
[15] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
[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). Heidelberg: Springer, 2012. P. 478–490. (Lect. Notes Comput. Sci.; Vol. 7464).
[17] Ahuja R. K., Magnanti T. L., Orlin J. B. Network flows: Theory, algorithms, and applications. Upper Saddle River, NJ: Prentice-Hall, 1993. 863 p.
[18] Корте Б., Фиген Й. Комбинаторная оптимизация: теория и алгоритмы. М: МЦНМО, 2015. 720 с.
[19] Cameron K. Coloured matchings in bipartite graphs // Discrete Math. 1997. Vol. 169. P. 205–209.
[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). New York: ACM, 1977. P. 1–10.
[21] Itai A., Rodeh M., Tanimoto S. L. Some matching problems for bipartite graphs // J. ACM. 1978. Vol. 25, No 4. P. 517–525.
[22] Papadimitriou C. H., Yannakakis M. The complexity of restricted spanning tree problems // J. ACM. 1982. Vol. 29, No 2. P. 285–309.
[23] Карзанов А. В. О максимальных паросочетаниях заданного веса в полных и полных двудольных графах // Кибернетика. 1987, № 1. С. 7–11.
[24] Zhu G., Luo X., Miao Y. Exact weight perfect matching of bipartite graph is NP-complete // Proc. World Congr. Engineering 2008 (London, UK, July 2–4, 2008). Vol. II. London: Newswood, 2008. P. 878–880.
[25] Gurjar R., Korwar A., Messner J., Thierauf T. Exact perfect matching in complete graphs // ACM Trans. Comput. Theory. 2017. Vol. 9, No. 2. P. 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. 2009. Vol. 35. P. 317–322.
[27] Gabow H. N., Tarjan R. E. Faster scaling algorithms for network problems // SIAM J. Comput. 1989. Vol. 18. P. 1013–1036.
[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). Piscataway: IEEE, 2012. P. 581–590.
[29] Gabow H. N., Tarjan R. E. Faster scaling algorithms for general graph matching problems // J. ACM. 1991. Vol. 38, No 4. P. 815–853.
