- 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 fluctuation in the random assignment problem Commun. Korean Math. Soc. 2002 Vol. 17, No. 2, 321-330 Printed June 1, 2002 Sungchul Lee, Zhonggen Su Yonsei University, Zhejiang University Abstract : Consider the random assignment (or bipartite matching) problem with iid uniform edge costs $t(i,j)$. Let $A_n$ be the optimal assignment cost. Just recently does Aldous \cite{A2001} give a rigorous proof that $EA_n \ra \zeta(2)$. In this paper we establish the upper and lower bounds for $\text{\rm Var} A_n$, i.e., there exist two strictly positive but finite constants $C_1$ and $C_2$ such that $C_1 n^{-5/2} (\log n)^{-3/2} \le \text{\rm Var} A_n \le C_2 n^{-1} (\log n)^{2}$. Keywords : assignment problem, bipartite matching, conditional variance, probabilistic analysis of algorithms 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