Title :
Distributed algorithms for biobjective assignment problems
Author :
Li, Chendong ; Park, Chulwoo ; Pattipati, Krishna R. ; Kleinman, David L.
Author_Institution :
Comput. Sci. Eng. Dept., Univ. of Connecticut, Storrs, CT, USA
Abstract :
In this paper, we study the biobjective assignment problem, a NP-hard version of the classical assignment problem. We employ an effective two-phase method with certain enhancements: in Phase I, we use a distributed auction algorithm to solve the single objective assignment problems to obtain the so-called supported Pareto optimal solutions; we apply a ranking approach with tight upper/lower bounds in Phase II to obtain the non-supported Pareto optimal solutions. Moreover, a randomized algorithm for Phase II is proposed that supports finding the approximation on a polynomial time basis. Extensive experiments are conducted using SGI Altix 3700 and computational results are reported based on a large set of randomly generated problem instances. Also, some experimental results of the distributed auction algorithm on large data-size assignment problems are provided.
Keywords :
Pareto optimisation; computational complexity; distributed algorithms; operations research; NP-hard version; SGI Altix 3700; biobjective assignment problem; distributed algorithms; distributed auction algorithm; nonsupported Pareto optimal solution; polynomial time basis approximation; randomized algorithm; randomly generated problem instances; ranking approach; single objective assignment problem; two-phase method; Algorithm design and analysis; Approximation algorithms; Context; Delta modulation; Planning; Upper bound; Xenon;
Conference_Titel :
Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on
Conference_Location :
Orlando, FL
Print_ISBN :
978-1-61284-800-6
Electronic_ISBN :
0743-1546
DOI :
10.1109/CDC.2011.6161434
