首页 | 本学科首页   官方微博 | 高级检索  
     


Algorithms for finding a Kth best valued assignment
Authors:Tomomi Matsui   Akihisa Tamura  Yoshiko Ikebe
Affiliation:

a Department of Industrial Administration, Science University of Tokyo, Noda, Chiba 278, Japan

b Department of Information Sciences, Tokyo Institute of Technology, 2-12-1 Oh-okayama, Meguro-ku, Tokyo 152, Japan

Abstract:We consider a new problem, the Kth best valued assignment problem. Given a bipartite graph G and a cost vector w on its edge set, this is the problem of finding a perfect matching Mk in G such that there exist perfect matchings M1,…,MK−1 satisfying w(M1) < < w(MK−1) < w(MK), and w(MK) < w(M) for all perfect matchings M with w(M) ≠ w(M1),…,w(MK). Here w(M) denotes the sum of costs of edges in M. In this paper, we propose two algorithms for solving this problem and verify the efficiency of our algorithms by our preliminary computational experiments.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号