- Current Issue - Ahead of Print Articles - All Issues - Search - Open Access - Information for Authors - Downloads - Guideline - Regulations ㆍPaper Submission ㆍPaper Reviewing ㆍPublication and Distribution - Code of Ethics - For Authors ㆍOnline Submission ㆍMy Manuscript - For Reviewers - For Editors
 On the random $n\times m$ assignment problem Commun. Korean Math. Soc. 2002 Vol. 17, No. 4, 719-729 Printed December 1, 2002 Sungchul Lee, Zhonggen Su Yonsei University, Zhejiang University Abstract : Consider the random $n\times m$ assignment problem with $m\ge n$. Let $u_{i,j}$ and $t_{i,j}$ be iid uniform random variables on $[0,1]$ and exponential random variables with mean 1, respectively, and let $U_{n,m}$ and $T_{n,m}$ denote the optimal assignment costs corresponding to $u_{i,j}$ and $t_{i,j}$. In this paper we first give a comparison result about the discrepancy $ET_{n,m}-EU_{n,m}$. Using this comparison result with a known lower bound for ${\rm Var}(T_{n,m})$ we obtains a lower bound for ${\rm Var}(U_{n,m})$. Finally, we study the way that $EU_{n,m}$ and $ET_{n,m}$ vary as $m$ does. It turns out that only when $m-n$ is large enough, the cost decreases significantly. Keywords : $n \times m$ assignment problem, bipartite matching, optimal assignment MSC numbers : Primary 05C70, 60C05, 68W40; Secondary 90C27 Downloads: Full-text PDF

 Copyright © Korean Mathematical Society. The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd