# A randomized algorithm for the on-line weighted bipartite matching problem - Computer Science > Data Structures and Algorithms

A randomized algorithm for the on-line weighted bipartite matching problem - Computer Science > Data Structures and Algorithms - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We study the on-line minimum weighted bipartite matching problem in arbitrarymetric spaces. Here, \$n\$ not necessary disjoint points of a metric space \$M\$are given, and are to be matched on-line with \$n\$ points of \$M\$ revealed one byone. The cost of a matching is the sum of the distances of the matched points,and the goal is to find or approximate its minimum. The competitive ratio ofthe deterministic problem is known to be \$\Theta(n)\$. It was conjectured that arandomized algorithm may perform better against an oblivious adversary, namelywith an expected competitive ratio \$\Theta(\log n)\$. We prove a slightly weakerresult by showing a \$o(\log^3 n)\$ upper bound on the expected competitiveratio. As an application the same upper bound holds for the notoriously hardfire station problem, where \$M\$ is the real line.

Autor: Béla Csaba (Anal. and Stoch. Res. Group, HAS), András S. Pluhár (Dept. of Comp. Sci., Univ. of Szeged)

Fuente: https://arxiv.org/