# Worst case examples of an exterior point algorithm for the assignment problem

Title | Worst case examples of an exterior point algorithm for the assignment problem |

Publication Type | Journal Articles |

Year of Publication | 2008 |

Authors | Papamanthou C, Paparrizos K, Samaras N, Stergiou K |

Journal | Discrete Optimization |

Volume | 5 |

Issue | 3 |

Pagination | 605 - 614 |

Date Published | 2008/08// |

ISBN Number | 1572-5286 |

Keywords | Assignment problem, Exterior point algorithm, Worst case examples |

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–54]. This algorithm belongs to the category of forest algorithms and solves an n × 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. |

URL | http://www.sciencedirect.com/science/article/pii/S1572528608000030 |

Short Title | Discrete Optimization |