Back to Search
Start Over
Distributed algorithms for biobjective assignment problems.
- Source :
- IEEE Conference on Decision & Control & European Control Conference; 1/ 1/2011, p5893-5898, 6p
- Publication Year :
- 2011
-
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. [ABSTRACT FROM PUBLISHER]
Details
- Language :
- English
- ISBNs :
- 9781612848006
- Database :
- Complementary Index
- Journal :
- IEEE Conference on Decision & Control & European Control Conference
- Publication Type :
- Conference
- Accession number :
- 86615707
- Full Text :
- https://doi.org/10.1109/CDC.2011.6161434