Geodesic
A weighted perfect matching with~constraints~on~weights of~its parts
Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 3, pp. 5-37

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: perfect matching, assignment problem, NP-hardness. 
@article{DA_2021_28_3_a0,
     author = {O. I. Duginov},
     title = {A weighted perfect matching with~constraints~on~weights of~its parts},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--37},
     publisher = {mathdoc},
     volume = {28},
     number = {3},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2021_28_3_a0/}
}
TY  - JOUR
AU  - O. I. Duginov
TI  - A weighted perfect matching with~constraints~on~weights of~its parts
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2021
SP  - 5
EP  - 37
VL  - 28
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2021_28_3_a0/
LA  - ru
ID  - DA_2021_28_3_a0
ER  - 
%0 Journal Article
%A O. I. Duginov
%T A weighted perfect matching with~constraints~on~weights of~its parts
%J Diskretnyj analiz i issledovanie operacij
%D 2021
%P 5-37
%V 28
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2021_28_3_a0/
%G ru
%F DA_2021_28_3_a0
O. I. Duginov. A weighted perfect matching with~constraints~on~weights of~its parts. Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 3, pp. 5-37. http://geodesic.mathdoc.fr/item/DA_2021_28_3_a0/