# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
A randomized algorithm for the on-line weighted bipartite matching problem. (English) Zbl 1176.68239
Summary: We study the on-line minimum weighted bipartite matching problem in arbitrary metric 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 by one. 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 of the deterministic problem is known to be ${\Theta }\left(n\right)$ [see B. Kalyanasundaram and K. Pruhs, J. Algorithms 14, No. 3, 478–488 (1993; Zbl 0768.68151), and S. Khuller, S. G. Mitchell and V. V. Vazirani, Theor. Comput. Sci. 127, No. 2, 255–267 (1994; Zbl 0938.68934)]. It was conjectured by B. Kalyanasundaram and K. Pruhs [Lect. Notes Comput. Sci. 1442, 268–280 (1998)] that a randomized algorithm may perform better against an oblivious adversary, namely with an expected competitive ratio ${\Theta }\left(logn\right)$. We prove a slightly weaker result by showing a $o\left({log}^{3}n\right)$ upper bound on the expected competitive ratio. As an application the same upper bound holds for the notoriously hard fire station problem, where $M$ is the real line [see B. Fuchs, W. Hochstättler and W. Kern, Theor. Comput. Sci. 332, No. 1–3, 251–264 (2005; Zbl 1070.68157), and E. Koutsoupias and A. Nanavati, Lect. Notes Comput. Sci. 2909, 179–191 (2004; Zbl 1173.68865)].
##### MSC:
 68W20 Randomized algorithms 68W27 Online algorithms
##### References:
 [1] Alon, N., Karp, R. M., Peleg, D., & West, D. (1995). A graph–theoretic game and its application to the k-server problem. SIAM Journal on Computing, 24(1), 78–100. · Zbl 0818.90147 · doi:10.1137/S0097539792224474 [2] Bartal, Y. (1996). Probabilistic approximations of metric spaces and its algorithmic applications. In IEEE symposium on foundations of computer science (pp. 184–193). [3] Bartal, Y. (1998). On approximating arbitrary metrics by tree metrics. In STOC. [4] Fakcharoenphol, J., Rao, S., & Talwar, K. (2004). A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences, 69(3), 485–497. · Zbl 1071.68082 · doi:10.1016/j.jcss.2004.04.011 [5] Fuchs, B., Hochstättler, W., & Kern, W. (2003). Online matching on a line. In H. Broersma, U. Faigle, J. Hurink, S. Pickl, G. Woeginger (Eds.), Electronic notes in discrete mathematics (Vol. 13). Amsterdam: Elsevier. [6] Kalyanasundaram, B., & Pruhs, K. (1993). Online weighted matching. Journal of Algorithms, 14(3), 478–488. · Zbl 0768.68151 · doi:10.1006/jagm.1993.1026 [7] Kalyanasundaram, B., & Pruhs, K. (1998). On-line network optimization problems. In A. Fiat & G. Woeginger (Eds.), Lecture notes in computer science : Vol. 1442. Online algorithms: the state of the art (pp. 268–280). Berlin: Springer. [8] Karp, R. (1989). A 2 k -competitive algorithm for the circle. Manuscript, August 1989 [9] Khuller, S., Mitchell, S. G., & Vazirani, V. V. (1994). On-line algorithms for weighted bipartite matching and stable marriages. Theoretical Computer Science, 127(2), 255–267. · doi:10.1016/0304-3975(94)90042-6 [10] Koutsoupias, E., & Nanavati, A. (2004). The online matching problem on a line. In Lecture notes in computer science : Vol. 2909. Approximation and online algorithms (pp. 179–191). Berlin: Springer. [11] Meyerson, A., Nanavati, A., & Poplawski, L. (2006). Randomized on-line algorithms for minimum metric bipartite matching. In SODA (pp. 954–959).