The Paired Assignment Problem ()
Abstract
We consider a variation of the maximum bipartite matching problem where
each completed task must have at least two agents assigned to it. We give an
integer programming formulation for the problem, and prove that the basic
solutions of LP-relaxation are half-integral. It is shown that a fractional
basic solution can be further processed to obtain an optimal solution to the
problem.
Share and Cite:
Melkonian, V. (2014) The Paired Assignment Problem.
Open Journal of Discrete Mathematics,
4, 44-54. doi:
10.4236/ojdm.2014.42007.
Conflicts of Interest
The authors declare no conflicts of interest.
References
|
[1]
|
Melkonian, V. (2011) Circuit Integration through Lattice Hyperterms. Discrete Mathematics, Algorithms and Applications, 3, 101-119.
|
|
[2]
|
Ahuja, R., Magnanti, T. and Orlin, J. (1994) Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood.
|
|
[3]
|
Alevras, D. (2009) Assignment and Matching. Encyclopedia of Optimization, 1, 106-108.
|
|
[4]
|
Lova’sz, L. and Plummer, M.D. (1986) Matching Theory. North-Holland, Amsterdam.
|
|
[5]
|
Goddard, W., Hedetniemi, S.M., Hedetniemi, S.T. and Laskar, R. (2005) Generalized Subgraph-Restricted Matchings in Graphs. Discrete Mathematics, 293, 129-138. http://dx.doi.org/10.1016/j.disc.2004.08.027
|
|
[6]
|
Pentico, D. (2007) Assignment Problems: A Golden Anniversary Survey. European Journal of Operational Research, 176, 774-793.
|
|
[7]
|
Aora, S. and Puri, M.C. (1998) A Variant of Time Minimizing Assignment Problem. European Journal of Operational Research, 110, 314-325. http://dx.doi.org/10.1016/S0377-2217(97)00266-X
|
|
[8]
|
Cattrysse, D.G. and Van Wassenhove, L.N. (1992) A Survey of Algorithms for the Generalized Assignment Problem. European Journal of Operational Research, 60, 260-272.
|
|
[9]
|
Chang, G.H. and Ho, P.-H. (1998) The b-Assignment Problem. European Journal of Operational Research, 104, 593-600. http://dx.doi.org/10.1016/S0377-2217(97)00008-8
|