Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1176.68239
Csaba, Béla; Pluhár, András
A randomized algorithm for the on-line weighted bipartite matching problem. (English)
[J] J. Sched. 11, No. 6, 449-455 (2008). ISSN 1094-6136; ISSN 1099-1425/e

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 (n)$ [see {\it B. Kalyanasundaram} and {\it K. Pruhs}, J. Algorithms 14, No.~3, 478--488 (1993; Zbl 0768.68151), and {\it S. Khuller, S. G. Mitchell} and {\it V. V. Vazirani}, Theor. Comput. Sci. 127, No.~2, 255--267 (1994; Zbl 0938.68934)]. It was conjectured by {\it B. Kalyanasundaram} and {\it 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 (\log n)$. We prove a slightly weaker result by showing a $o(\log ^{3} n)$ 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 {\it B. Fuchs, W. Hochstättler} and {\it W. Kern}, Theor. Comput. Sci. 332, No.~1--3, 251--264 (2005; Zbl 1070.68157), and {\it E. Koutsoupias} and {\it A. Nanavati}, Lect. Notes Comput. Sci. 2909, 179--191 (2004; Zbl 1173.68865)].

MSC 2000:: *68W20 Randomized algorithms
68W27

Citations: Zbl 0768.68151; Zbl 0938.68934; Zbl 1070.68157; Zbl 1173.68865

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]