Please use this identifier to cite or link to this item:
Title: On the initialization methods of an exterior point algorithm for the assignment problem
Authors: Papamanthou, C.
Paparrizos, Konstantinos
Samaras, Nikolaos
Sifaleras, Angelo
Type: Article
Subjects: FRASCATI::Natural sciences::Mathematics::Applied Mathematics
FRASCATI::Natural sciences::Computer and information sciences
Keywords: Combinatorial optimization
Assignment problem
Exterior point algorithm
Initialization methods
Computational evaluation
Issue Date: 2010
Publisher: Taylor & Francis
Source: International Journal of Computer Mathematics
Volume: 87
Issue: 8
First Page: 1831
Last Page: 1846
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.
ISSN: 0020-7160
Other Identifiers: 10.1080/00207160802524739
Appears in Collections:Department of Applied Informatics

Files in This Item:
File Description SizeFormat 
On_the_initialization_methods_of_an_exterior_point_algorithm_for_the_assignment_problem.pdf202,9 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.