68
Views
3
CrossRef citations to date
0
Altmetric
Section B

On the initialization methods of an exterior point algorithm for the assignment problem

, , &
Pages 1831-1846 | Received 24 Jul 2007, Accepted 20 Sep 2008, Published online: 01 Jul 2009
 

Abstract

In this paper, we present a theoretical investigation and an extensive computational study of exterior point simplex algorithm (EPSA) initialization methods for the assignment problem (AP). We describe the exterior point algorithm using three different initialization methods. Effective implementations are explored for each initialization method. Then we perform an experimental evaluation on a large set of benchmark problems from the TSPLib 95 and OR Library collections. The results obtained demonstrate the advantages of the three initialization methods. Finally, we give a theoretical justification of the initialization methods efficiency. We explain theoretically the computational ranking for these methods.

AMS Subject Classification :

View correction statement:
On the initialization methods of an exterior point algorithm for the assignment problem

Acknowledgements

The authors wish to thank the anonymous reviewers for some very crucial comments and suggestions that helped them in improving the quality of the paper.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.