Source-linked AI summary
Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations
Gagan Aggarwal, Gagan Goel, Chinmay Karande, Aranyak Mehta
TL;DR
The paper studies online bipartite matching with known, weighted offline vertices and irrevocable online arrivals, extending the unweighted problem and addressing the single-bid budgeted-allocation case. It uses independent random multiplicative perturbations of weights, and Perturbed-Greedy achieves the optimal 1−1/e competitive ratio, while connecting to MSVV for large capacities.
Problem
Vertex-weighted online matching requires maximizing matched offline weight rather than cardinality, and the single-bid budgeted-allocation case lacked a solution when bids could be comparable to budgets.
Method
Perturbed-Greedy independently perturbs each offline vertex weight by a random multiplicative factor before making greedy online matches.
Results
1−1/e competitive ratio is achieved optimally for vertex-weighted online bipartite matching and for the single-bid budgeted-allocation case.
Takeaways & Limitations
The algorithm generalizes Ranking, offers connections to MSVV as capacities grow, and suggests a unified approach to online budgeted allocation.
Takeaways & Limitations
The warm-up analysis assumes equal-sized sides and a perfect matching, while a proof remark identifies difficulties combining losses across overlapping occurrences.
Abstract
from arXiv · showhide
We study the following vertex-weighted online bipartite matching problem: $G(U, V, E)$ is a bipartite graph. The vertices in $U$ have weights and are known ahead of time, while the vertices in $V$ arrive online in an arbitrary order and have to be matched upon arrival. The goal is to maximize the sum of weights of the matched vertices in $U$. When all the weights are equal, this reduces to the classic \emph{online bipartite matching} problem for which Karp, Vazirani and Vazirani gave an optimal $\left(1-\frac{1}{e}\right)$-competitive algorithm in their seminal work~\cite{KVV90}. Our main result is an optimal $\left(1-\frac{1}{e}\right)$-competitive randomized algorithm for general vertex weights. We use \emph{random perturbations} of weights by appropriately chosen multiplicative factors. Our solution constitutes the first known generalization of the algorithm in~\cite{KVV90} in this model and provides new insights into the role of randomization in online allocation problems. It also effectively solves the problem of \emph{online budgeted allocations} \cite{MSVV05} in the case when an agent makes the same bid for any desired item, even if the bid is comparable to his budget - complementing the results of \cite{MSVV05, BJN07} which apply when the bids are much smaller than the budgets.
1 Introduction
The paper formulates vertex-weighted online bipartite matching, where irrevocable online decisions must maximize the total weight of matched offline vertices. It introduces independent random weight perturbations, achieving the optimal unweighted competitive ratio and extending the result to single-bid budgeted allocation.
- Problem formulation: Vertex-weighted matching maximizes the total weight of offline vertices matched to online arrivals under irrevocable decisions.Offline vertices and their weights are known in advance; online vertices arrive in arbitrary order and reveal their incident edges.
- Main result: Independent random perturbations of vertex weights generalize Ranking while connecting the strengths of Greedy and Ranking across weight regimes.Greedy performs well with highly skewed weights, whereas Ranking performs well with equal weights.
- Main result: 1−1/e competitive ratio is achieved optimally by Perturbed-Greedy for vertex-weighted online bipartite matching.No randomized algorithm can obtain a better competitive ratio.
- Budgeted allocation: 1−1/e competitive ratio is achieved for the single-bid case of online budgeted allocation.This case has equal nonzero bids for each agent’s desired items and reduces to vertex-weighted matching.
- Budgeted allocation: Perturbed-Greedy converges in expectation to MSVV as capacities grow large in the single small-bids case.With large capacities, the perturbation multiplier corresponds in expectation to the fraction of capacity already used.
- Implications: The shared perturbation function provides a smooth interface between single-bid and small-bid allocation settings and suggests a unified general solution.The paper emphasizes that this connection is not merely due to choosing the same function, because the two analyses use different foundations.
2 Preliminaries
The paper formalizes vertex-weighted online bipartite matching and reviews Ranking as a warm-up for analyzing the unweighted case. The warm-up uses random permutations, charging between unmatched and matched events, and establishes the 1−1/e benchmark under simplifying assumptions.
- Problem statement: The online problem reveals each arriving vertex’s incident edges and requires an irrevocable match or permanent rejection.The offline vertices and their weights are known in advance, and the objective is the total weight of matched offline vertices.
- Competitive analysis: The competitive ratio compares the online algorithm’s gain with an optimal offline matching over the worst graph and arrival order.The offline optimum depends only on the graph, whereas the online gain depends on the arrival permutation.
- Ranking: Ranking samples a uniformly random permutation of offline vertices and matches each arriving vertex to its earliest-ranked unmatched neighbor.This randomized rule is analyzed as the unweighted special case and warm-up for the paper’s main result.
- Warm-up assumptions: Under |U|=|V|=n and a perfect matching, the warm-up has OPT=n and fixes a perfect optimal matching for analysis.These assumptions simplify the proof rather than define the general vertex-weighted problem.
3 Proof Of Theorem 1
The proof analyzes a discretized Perturbed-Greedy algorithm through random positions, matched and unmatched events, and charging maps. It establishes structural properties of perturbation-induced matching changes and resolves charging-map overlap using marginal loss.
- Algorithm: The discrete proof chooses σ(u) uniformly from {1,...,k}, uses decreasing ψ(i), and converges to the original algorithm as k grows.The discrete algorithm preserves the same maximum perturbed-weight matching rule.
- Charging analysis: The analysis partitions probability-space occurrences into matched events Q_t and unmatched events R_t, then maps bad events to good events while comparing scaled gains and losses.The charging map is designed to bound unmatched occurrences by matched ones.
- Charging analysis: Unlike Ranking, charging-map targets may occur at positions above or below the bad event, producing a weak bound based on a broad union of matched events.Summing losses across positions would use more events but can destroy disjointness.
- Charging analysis: The proof handles overlap by introducing marginal loss, which supports a disjoint map and yields a tight bound.Earlier attempts fail because occurrences from different positions can map to the same event.
- Structural lemmas: When one weight is moved to a different perturbation position, the matching differences form a single arrival-ordered alternating path starting at that vertex.This structural property underlies the proof of the corresponding matching and charging lemmas.
A The Reduction from Online Budgeted Allocation with Single Bids
The section reduces single-bid online budgeted allocation to vertex-weighted online matching by representing each agent’s budget as weighted vertices. The two solution mappings preserve or increase objective value, transferring guarantees between the problems.
- Reduction: Single-bid online budgeted allocation is reduced to online vertex-weighted bipartite matching.Each item becomes an online vertex, while each agent is represented by one or more offline vertices.
- Reduction: For agent i, the construction creates n_i vertices of weight b_i and, when needed, one residual vertex of weight r_i=B_i−n_ib_i.Here n_i is the largest integer satisfying n_ib_i≤B_i, and r_i<b_i.
- Reduction: Edges connect an agent’s constructed vertices to exactly those item vertices on which the agent places a non-zero bid.Thus, adjacency captures item eligibility under single bids.
- Objective preservation: A budgeted allocation can be converted into a matching with the same total value.Items allocated to an agent are matched to that agent’s constructed vertices, with separate cases for payments below or at the budget.
- Objective preservation: A matching can be converted into a budgeted allocation with at least the same total value.The construction allocates each matched item to the corresponding agent and handles both unsaturated and saturated cases.
B Performance of Greedy and Ranking
Greedy and Ranking each perform well on different weight regimes but can be poor on the other regime. Greedy guarantees 1/2 competitively, and this factor is tight.
- Greedy: Greedy matches each arriving vertex to an unmatched neighbor of maximum weight.Ties may be broken arbitrarily.
- Greedy: 1/2: Greedy achieves a competitive ratio of 1/2 in vertex-weighted online bipartite matching.The proof charges every optimal vertex missed by Greedy to a Greedy-matched vertex of at least as large weight.
- Greedy: 1/2: The Greedy guarantee is tight as the gadget parameter ϵ approaches zero.The construction uses many copies of a four-vertex gadget.
- Comparison: Greedy performs well for highly skewed weights, whereas Ranking performs well when weights are roughly equal.Neither strategy is uniformly effective across both regimes.
C Intuition Behind the Sufficiency of Independent Perturbations
Independent perturbations are motivated by instances with identical vertex weights but different graph structures, which favor different strategies. This suggests that the offline weight vector alone need not determine the best strategy.
- Independent perturbations: Independent perturbations are sufficient for the algorithm’s best-possible competitive ratio, despite the offline availability of the full weight vector.The paper presents this as a post-facto conclusion about the perturbation design.
- Instance intuition: Two instances with identical vertex weights can require widely differing optimal strategies because their graph structures differ.Figure 1 illustrates the pair of instances.
- Instance intuition: Ranking is favored by equal-weight components in one instance, while Greedy is suggested by highly skewed-weight components in the other.The examples also show that each strategy can be far from optimal on the opposite instance.
D Hard Instances in 2 × 2 Graphs
Figure 2 identifies the only two potentially hard instances among 2×2 graphs; all other instances are optimally handled by a reasonable greedy rule.
- Only two potentially hard instances occur in 2×2 graphs.The passage refers to Figure 2 as showing these canonical examples.
- On all other instances, the optimal matching is found by leaving an arriving vertex unmatched only when all its neighbors are already matched.
- Figure 2 provides canonical examples for 2×2 graphs.
E Marginal Loss Events
Figure 3 is titled “Marginal Losses,” indicating that this section presents marginal-loss events.
- Figure 3 is titled “Marginal Losses.”
- The supplied passage identifies Figure 3 as a figure about marginal losses.
- The figure is presented as part of the section on marginal-loss events.
F Graphs with Imperfect Matchings
The proof extends Theorem 1 from balanced graphs with perfect matchings to general graphs by modifying definitions and equations while retaining Perturbed-Greedy.
- Theorem 1 is extended beyond graphs with |U| = |V| and a perfect matching.
- The algorithm remains unchanged: it continues to use Perturbed-Greedy.
- For a maximum-weight matching M*(G), the proof considers the vertices in U matched by M*(G).
- The proof updates the definitions of R_t and the associated equations to reflect this change.
- Vertices not matched by M*(G) are no longer treated as producing bad events when unmatched.
- The version of equation (16) for each t is weighted by ψ(t) − ψ(t + 1) and summed over t, with ψ(k + 1) = 0.
G A Lower Bound for Randomized Algorithms with Edge Weights
This section establishes a lower bound for randomized online matching with edge weights under scale-free algorithms. Using Yao’s principle and a single-vertex construction, it concludes that the best such competitive ratio is O(1/n).
- The section studies randomized online matching with edge weights, maximizing the total weight of matched edges.
- The lower-bound proof is restricted to scale-free algorithms, which make the same matching decisions after uniformly scaling all edge weights.
- Yao’s principle reduces the argument to constructing a distribution over arriving edge weights that defeats deterministic algorithms in expectation.
- The hard instance has one vertex u in U, with every arriving vertex in V connected to u by an edge of weight b_v.
- Scale-freeness prevents the algorithm from distinguishing weight vectors after the first k arrivals, characterizing it by the first positive-weight match position k.
- O(1/n) is the resulting competitive-ratio bound for the best scale-free randomized algorithm.