Algorithms for finding a Kth best valued assignment

Tomomi Matsui; Akihisa Tamura; Yoshiko Ikebe

doi:10.1016/0166-218X(92)00175-L

Algorithms for finding a Kth best valued assignment

Tomomi Matsui
, Akihisa Tamura
, Yoshiko Ikebe

研究成果: Article › 査読

3 被引用数 (Scopus)

抄録

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 M_k in G such that there exist perfect matchings M₁,...,M_K-1 satisfying w(M₁) < ⋯ < w(M_K-1) < w(M_K), and w(M_K) < w(M) for all perfect matchings M with w(M) ≠ w(M₁),...,w(M_K). 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.

本文言語	English
ページ（範囲）	283-296
ページ数	14
ジャーナル	Discrete Applied Mathematics
巻	50
号	3
DOI	https://doi.org/10.1016/0166-218X(92)00175-L
出版ステータス	Published - 1994 5月 20
外部発表	はい

ASJC Scopus subject areas

離散数学と組合せ数学
応用数学

文献へのアクセス

10.1016/0166-218X(92)00175-L

他のファイルとリンク

引用スタイル

@article{6f3cf164e8654d138744a0f66628136f,

title = "Algorithms for finding a Kth best valued assignment",

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.",

author = "Tomomi Matsui and Akihisa Tamura and Yoshiko Ikebe",

year = "1994",

month = may,

day = "20",

doi = "10.1016/0166-218X(92)00175-L",

language = "English",

volume = "50",

pages = "283--296",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Algorithms for finding a Kth best valued assignment

AU - Matsui, Tomomi

AU - Tamura, Akihisa

AU - Ikebe, Yoshiko

PY - 1994/5/20

Y1 - 1994/5/20

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/38149147151

UR - https://www.scopus.com/pages/publications/38149147151#tab=citedBy

U2 - 10.1016/0166-218X(92)00175-L

DO - 10.1016/0166-218X(92)00175-L

M3 - Article

AN - SCOPUS:38149147151

SN - 0166-218X

VL - 50

SP - 283

EP - 296

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 3

ER -

Algorithms for finding a Kth best valued assignment

抄録

ASJC Scopus subject areas

文献へのアクセス

他のファイルとリンク

フィンガープリント

引用スタイル