A new algorithm for the quasi-assignment problem |
| |
Authors: | Tiantai Song Li Zhou |
| |
Institution: | (1) Institute of Applied Mathematics, Academia Sinica, Beijing, P.R. China |
| |
Abstract: | The quasi-assignment problem can be used to solve the bus scheduling problem, the tourist guide problem, and the minimum number of chains in a partially ordered set. A successive shortest path algorithm for the assignment problem is extended to the quasiassignment problem. The algorithm is a variation of the primal-dual algorithm, and its computational complexity isO(n
3).The research for this paper was partly supported by the Chinese National Science Foundation. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|