Abstract
We show that certain manpower scheduling problems can be modeled as the following constrained matching problem. Given an undirected graphG = (V,E) with edge weights and a digraphD = (V,A). AMaster/Slave-matching (MS-matching) ofG with respect toD is a matching ofG such that for each arc (u, v) εA for which the nodeu is matched, the nodev is matched, too. TheMS-Matching Problem is the problem of finding a maximum-weight MS-matching. Letk(D) be the maximum size of a (weakly) connected component ofD. We prove that MS-matching is an NP-hard problem even ifG is bipartite andk(D) ≤ 3. Moreover, we show that in the relevant special case wherek(D) ≤ 2, the MS-Matching Problem can be transformed to the ordinary Matching Problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. Aboudi and K. Jørnsten, Resource constrained assignment problems, Discr. Appl. Math. 26(1990)175–191.
R. Aboudi and G.L. Nemhauser, An assignment problem with side constraints: strong cutting planes and separation, in:Economic Decision Making: Games, Econometrics and Optimization, ed. J.J. Gabszewicz et al. (Elsevier, 1990) pp. 457–471.
R. Aboudi and G.L. Nemhauser, Some facets for an assignment problem with side constraints, Oper. Res. 39(1991)244–250.
V. Aggarwal, A Lagrangian-relaxation method for the constrained assignment problem, Comp. Oper. Res. 12(1985)97–106.
E. Balas, The prize collecting traveling salesman problem, Networks 19(1989)621–636.
M.O. Ball, U. Derigs, C. Hildebrand and A. Metz, Matching problems with generalized upper bound side constraints, Networks 20(1990)703–721.
M.R. Garey and D.S. Johnson,Computers and Intractability (Freeman, New York, 1979).
A. Hefner, A min.max theorem for a constrained matching problem, submitted to SIAM J. Discr. Math. (1995).
A. Itai, M. Rodeh and S.L. Tanimoto, Some matching problems for bipartite graphs, J. ACM 25(1978)517–525.
D. König, Gráfok és alkalmazásuk a determinánsok és halmazok elméletében, Mathematikai és Természettudományi Értesitö 34(1916)104–119 (in Hungarian).
[German transl.: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Mathematische Annalen 77(1916)453–465.]
E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976).
J.B. Mazzola and A.W. Neebe, Resource-constrained assignment scheduling, Oper. Res. 34(1986)560–572.
M. Padberg and A. Sassano, The complexity of matching with bonds, Inf. Proc. Lett. 32(1989)297–300.
C.H. Papadimitriou and K. Steiglitz,Combinatorial Optimization (Prentice-Hall, Englewood Cliffs, NJ, 1982).
Author information
Authors and Affiliations
Additional information
This research was supported by Grant 03-KL7PAS-6 of the German Federal Ministry of Research and Technology.
Rights and permissions
About this article
Cite this article
Hefner, A., Kleinschmidt, P. A constrained matching problem. Ann Oper Res 57, 135–145 (1995). https://doi.org/10.1007/BF02099694
Issue Date:
DOI: https://doi.org/10.1007/BF02099694