A randomized algorithm for the on-line weighted bipartite matching problem

DOI10.1007/S10951-007-0037-5MaRDI QIDQ835627zbMATH OpenOpenAlexFDO

Authors Béla Csaba, András Pluhár

Publication date 28 August 2009

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0705.4673

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20)

Abstract: 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)$. It was conjectured that a randomized algorithm may perform better against an oblivious adversary, namely with an expected competitive ratio $Theta(logn)$. We prove a slightly weaker result by showing a $o(lo{g}^{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.

Recommendations

• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
• Online Weighted Matching
• scientific article; zbMATH DE number 176778
• A randomized O(^2k)-competitive algorithm for metric bipartite matching
• Approximation and Online Algorithms

Cites work

• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• scientific article; zbMATH DE number 2230243 (Why is no real title available?)
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A tight bound on approximating arbitrary metrics by tree metrics
• Approximation and Online Algorithms
• On-line algorithms for weighted bipartite matching and stable marriages
• Online Weighted Matching
• Randomized online algorithms for minimum metric bipartite matching

Cited in

(10)

• Randomized algorithm for the \(k\)-server problem on decomposable spaces
• Competitive strategies for an online generalized assignment problem with a service consecution constraint
• scientific article; zbMATH DE number 176778 (Why is no real title available?)
• scientific article; zbMATH DE number 7376006 (Why is no real title available?)
• Online Weighted Matching
• Online perfect matching and mobile computing
• Greedy metric minimum online matchings with random arrivals
• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
• A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
• On the lower bound of the competitive ratio for the weighted online roommates problem

This page was built for publication: A randomized algorithm for the on-line weighted bipartite matching problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q835627)