A randomized algorithm for the on-line weighted bipartite matching problem - Computer Science > Data Structures and AlgorithmsReportar como inadecuado




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/







Documentos relacionados