Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/CDC.2011.6161434 | 2011 50TH IEEE CONFERENCE ON DECISION AND CONTROL AND EUROPEAN CONTROL CONFERENCE (CDC-ECC) |
Keywords | Field | DocType |
assignment problem,algorithm design,distributed algorithm,operations research,distributed algorithms,lower bound,algorithm design and analysis,approximation algorithms,delta modulation,randomized algorithm,upper bound,polynomial time,planning,xenon,computational complexity | Weapon target assignment problem,Approximation algorithm,Randomized algorithm,Mathematical optimization,Computer science,Generalized assignment problem,Assignment problem,Distributed algorithm,Auction algorithm,Linear bottleneck assignment problem | Conference |
ISSN | Citations | PageRank |
0743-1546 | 0 | 0.34 |
References | Authors | |
15 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chendong Li | 1 | 6 | 4.59 |
| Chulwoo Park | 2 | 10 | 3.25 |
| Krishna R. Pattipati | 3 | 506 | 82.13 |
| David L. Kleinman | 4 | 72 | 19.73 |