Open Journal of Discrete Mathematics

Volume 4, Issue 2 (April 2014)

ISSN Print: 2161-7635   ISSN Online: 2161-7643

Google-based Impact Factor: 0.64  Citations  

The Paired Assignment Problem

HTML  XML Download Download as PDF (Size: 573KB)  PP. 44-54  
DOI: 10.4236/ojdm.2014.42007    4,517 Downloads   7,145 Views  Citations
Author(s)

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.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.