Randomized algorithms for the on-line minimum matching problem on euclidean space

References

• Bertsimas , D. J. and Ryzin , G. V. 1990 . An asymptotic determination of the minimum spanning tree and minimum constants in geometrical probability . Operations Research Letters , 9 : 223 – 231 .
   Google Scholar
• Coffman , E. G. Jr. , Courcoubetis , C. , Garey , M. R. , Johnson , D. S. , Mc Geoch , L. A. , Shor , P. W. , Weber , R. and Yannakakis , M. 1991 . Proceedings of the 23rd ACM Symposium on Theory of Computing . Fundamental discrepancies between average-case analysis under discrete and continuous distributions: A bin packing case study . 1991 . pp. 230 – 241 .
   Google Scholar
• Coffman , E. G. Jr. , Hofri , M. , So , K. and Yao , A. C. 1980 . A stochastic model of bin packing . Information and Control , 44 105 – 115 .
   Google Scholar
• Graham , R. L. , Knuth , D. E. and Patashnik , O. 1989 . Concrete Mathematics , Addison-Wesley Publishing Company .
   Google Scholar
• Irani , S. and Rubinfeld , R. 1991 . A competitive 2-server algorithm . Information Processing Letters , 39 : 85 – 91 .
   Google Scholar
• Kalyanasundaram , B. and Pruhs , K. 1993 . On-line weighted matching . Journal of Algorithms , 14 : 478 – 488 .
   Google Scholar
• Karmarkar , N. 1982 . Proceedings of the 23rd Symposium on Foundations of Computer Science . Probabilistic analysis of some bin-packing algorithms . 1982 . pp. 107 – 111 .
   Google Scholar
• Khuller S. Mitchell S. Vazirani V. On-line algorithms for weighted matching and stable marriages Technical Report TR 90-1143 Department of Computer Science, Cornell University 1990
   Google Scholar
• Lee , C. C. and Lee , D. T. 1985 . A simple on-line bin-packing algorithm . Journal of the Association for computing Machinery , 32 ( 3 ) : 562 – 572 .
   Web of Science ®Google Scholar
• Raghavan , P. and Snir , M. 1989 . 16th International Colloquium on Automata, Languages, and Programming . Memory versus randomization in on-line algorithms . July 1989 . Vol. 372 , pp. 687 – 703 . Lecture Notes in Computer Science
   Google Scholar
• Ramanan , P. and Tsuga , K. 1989 . Average-case analysis of the modified harmonic algorithm . Algorithimica , 4 519 – 533 .
   Google Scholar
• Shor , P. W. 1986 . The average-case analysis of some on-line algorithms for bin packing . Combinatorica , 6 179 – 200 .
   Web of Science ®Google Scholar
• Sleator , D. D. and Tarjan , R. E. 1985 . Amortized efficiency of list update and paging rules . Commun. ACM , 28 ( 2 ) 202 – 208 .
   Web of Science ®Google Scholar
• Tsai , Y. T. , Tang , C. Y. and Chen , Y. Y. 1994 . “ Average Performance of a greedy algorithm for the on-line minimum matching problem on Euclidean space ” . In To appear in Information Processing Letters
   Google Scholar
• Vitter , J. S. and Krishnan , P. 1991 . Proceedings of the 32nd Symposium on Foundations of Computer Science . Optimal prefetching via data compression . 1991 . pp. 121 – 130 .
   Google Scholar
• Ming-Yang Baby Wang and Ruei-Chuan Chang . 1989 . An upper bound for the average length of the Euclidean minimum spanning tree . Intern. J. Computer. Math , 30 1 – 12 .
   Google Scholar