@article {19616,
	title = {Worst case examples of an exterior point algorithm for the assignment problem},
	journal = {Discrete Optimization},
	volume = {5},
	year = {2008},
	month = {2008/08//},
	pages = {605 - 614},
	abstract = {An efficient exterior point simplex type algorithm for the assignment problem has been developed by Paparrizos~[K. Paparrizos, An infeasible (exterior point) simplex algorithm for assignment problems, Math. Program. 51 (1991) 45{\textendash}54]. This algorithm belongs to the category of forest algorithms and solves an n {\texttimes} n assignment problem in at most n ( n - 1 ) 2 iterations and in at most O ( n 3 ) time. In this paper worst case examples are presented. Specifically, a systematic procedure to construct worst case assignment problems is presented for the exterior point algorithm. The algorithm applied to these examples executes exactly n ( n - 1 ) 2 iterations. This result verifies that the bound O ( n 3 ) is the best possible for the above-mentioned algorithm.},
	keywords = {Assignment problem, Exterior point algorithm, Worst case examples},
	isbn = {1572-5286},
	url = {http://www.sciencedirect.com/science/article/pii/S1572528608000030},
	author = {Charalampos Papamanthou and Paparrizos, Konstantinos and Samaras, Nikolaos and Stergiou, Konstantinos}
}
