Online Bipartite Matching is a fundamental algorithmic challenge where one aims to match elements from two disjoint sets as one side’s elements arrive sequentially, without knowledge of future arrivals. This dynamic approach is essential in real-time applications such as online ad allocation, ride-sharing platforms, and job assignments, where decisions must be made instantly.
What is Bipartite Matching?
A bipartite graph consists of two disjoint sets of vertices, usually denoted as U and V, with edges only running between these sets—not within them. A bipartite matching is a set of edges such that no two edges share a vertex, effectively pairing elements from U to V without overlap.
In classical bipartite matching, the entire graph is known upfront, allowing offline algorithms like the Hungarian Algorithm to find the maximum matching. However, in many real-world problems, one set arrives over time — this brings us to the online bipartite matching problem.
Understanding Online Bipartite Matching
In the online setting, one part of the bipartite graph is known in advance (offline nodes, say set U), and the other part (online nodes, say set V) arrives one at a time in unknown order. Upon each arrival of a vertex in V, the algorithm must immediately and irrevocably decide which vertex in U to match it with or leave it unmatched.
The goal is to maximize the size (or sometimes total weight) of the matching under these constraints.
Real-World Illustration
Imagine U as taxi drivers waiting in a city and V as passengers requesting rides in real-time. When a passenger arrives, the system must instantly assign an available driver to that passenger or reject the match, with no knowledge of future passenger requests.
Key Algorithms for Online Bipartite Matching
1. Greedy Algorithm
The simplest approach is a greedy algorithm:
- When an online vertex arrives, match it immediately to any free offline vertex connected to it.
- If multiple are available, pick one arbitrarily.
While simple, this algorithm can perform poorly — up to half the optimal matching in worst cases.
Example:
Suppose U = {U1, U2} and online vertices V arrive as V1 connected only to U1, and then V2 connected to both U1 and U2.
If the greedy matches V1 to U1 immediately, when V2 arrives it can only go to U2, achieving a matching of size 2, which is optimal here. But if V2 arrives first and is matched to U1, then V1 cannot be matched at all, reducing the total matching size.
2. Karp-Vazirani-Vazirani (KVV) Algorithm
This algorithm achieves a strong approximation ratio of 1 – 1/e (~0.63), which is the best possible for the problem without extra constraints.
How it works:
- Before the arrivals start, assign a uniformly random permutation (rank) to the offline vertices.
- When each online vertex arrives, match it to the free neighbor with the highest priority (lowest rank) according to this permutation.
Visual Example: KVV in Action
Consider three offline nodes U1, U2, U3 ranked in order of priority: U2 < U3 < U1. Online nodes arrive one by one:
- V1 arrives: connected to U2 and U3; chooses U2 (lowest rank available).
- V2 arrives: connected to U3; chooses U3 (free and next best rank).
- V3 arrives: connected to U1; chooses U1 (free).
This yields a perfect online matching covering all three online vertices.
Interactive Code Example (JavaScript) to Visualize Online Matching
The following snippet simulates the KVV algorithm with a dynamic interface to add online vertices and see matching:
class OnlineMatching {
constructor(offlineNodes) {
this.offlineNodes = offlineNodes;
this.rank = this._assignRanks(offlineNodes);
this.matched = new Set();
this.matching = {};
}
_assignRanks(nodes) {
// Assign a random permutation rank map
let shuffled = nodes.slice();
for(let i = shuffled.length-1; i > 0; i--) {
let j = Math.floor(Math.random()*(i+1));
[shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]];
}
let rankMap = {};
shuffled.forEach((node, i) => rankMap[node] = i);
return rankMap;
}
onOnlineArrival(onlineNode, neighbors) {
// neighbors: array of offline nodes connected to this online vertex
let candidates = neighbors.filter(n => !this.matched.has(n));
if (candidates.length === 0) return null; // no match
// Choose according to KVV priority
candidates.sort((a,b) => this.rank[a] - this.rank[b]);
let chosen = candidates[0];
this.matched.add(chosen);
this.matching[onlineNode] = chosen;
return chosen;
}
}
// Usage example
let offlineNodes = ['U1','U2','U3'];
let om = new OnlineMatching(offlineNodes);
console.log("Match V1:", om.onOnlineArrival('V1', ['U2','U3']));
console.log("Match V2:", om.onOnlineArrival('V2', ['U3']));
console.log("Match V3:", om.onOnlineArrival('V3', ['U1']));
console.log("Current matching:", om.matching);
Use Cases for Online Bipartite Matching
- Online Ads Allocation: Matching ad slots (offline) to arriving users or queries (online).
- Real-Time Job Assignment: Assigning tasks to available processors or workers arriving over time.
- Ride-Hailing and Delivery: Matching drivers to incoming ride or delivery requests instantly.
- Real-Time Resource Allocation: In networks or cloud computing, dynamically matching resources to demands.
Challenges and Performance Metrics
The inherent challenge lies in the uncertainty about future arrivals, limiting the algorithm’s ability to optimize globally. Hence, online bipartite matching algorithms are generally judged by competitive ratio, i.e., the ratio of the online algorithm’s matching size to the offline optimal maximum matching.
Summary
Online bipartite matching is a powerful model balancing real-time responsiveness and optimal resource utilization. From basic greedy heuristics to sophisticated algorithms like KVV, different approaches suit different applications and desired guarantees. Understanding these algorithms enables developers and researchers to implement efficient real-time matching systems.
