Multiplicative auction algorithm for approximate maximum weight bipartite matching

Abstract

We present an auction algorithm using multiplicative instead of constant weight updates to compute a $(1-\varepsilon )$-approximate maximum weight matching (MWM) in a bipartite graph with n vertices and m edges in time $O(m\varepsilon ^{-1})$, beating the running time of the fastest known approximation algorithm of Duan and Pettie [JACM ’14] that runs in $O(m\varepsilon ^{-1}\log \varepsilon ^{-1})$. Our algorithm is very simple and it can be extended to give a dynamic data structure that maintains a $(1-\varepsilon )$-approximate maximum weight matching under (1) one-sided vertex deletions (with incident edges) and (2) one-sided vertex insertions (with incident edges sorted by weight) to the other side. The total time time used is $O(m\varepsilon ^{-1})$, where m is the sum of the number of initially existing and inserted edges.

1 Introduction

Let $G = (U \cup V, E)$ be an edge-weighted bipartite graph with $n = |U\cup V|$ vertices and $m = |E|$ edges where each edge $uv \in E$ with $u\in U$ and $v\in V$ has a non-negative weight w(uv). The maximum weight matching (MWM) problem asks for a matching $M \subseteq E$ that attains the largest possible weight $w(M) = \sum _{uv\in M} w(uv)$. This paper will focus on approximate solutions to the MWM problem. More specifically, if we let $M^*$ denote a maximum weight matching of G, our goal is to find a matching M such that $w(M) \ge (1-\varepsilon ) w(M^*)$ for any small constant $\varepsilon >0$.

Matchings are a very well studied problem in combinatorial optimization. Kuhn [18] in 1955 published a paper that started algorithmic work in matchings, and presented what he called the “Hungarian algorithm” which he attributed the work to Kőnig and Egerváry. Munkres [21] showed that this algorithm runs in $O(n^4)$ time. The running time for computing the exact MWM has been improved many times since then. Recently, Chen et al. [11] showed that it was possible to solve the more general problem of max flow in $O(m^{1+o(1)})$ time.

For $(1-\varepsilon )$-approximation algorithms for MWM in bipartite graphs, Gabow and Tarjan in 1989 showed an $O(m\sqrt{n}\log (n/\varepsilon ))$ algorithm. Since then there were a number of results for different running times and different approximation ratios. The prior best approximate algorithm is by Duan and Pettie [13] which computes a $(1-\varepsilon )$-approximate maximum weight matching in $O(m\varepsilon ^{-1}\log (\varepsilon ^{-1}))$ time with a scaling algorithm. We defer to their work for a more thorough survey of the history on the MWM problem.

We show in our work that the auction algorithm for matchings using multiplicative weights can give a $(1-\varepsilon )$-approximate maximum weight matching with a running time of $O(m\varepsilon ^{-1})$ for bipartite graphs. This is a modest improvement of a $\log \varepsilon ^{-1}$ factor over the prior algorithm of Duan and Pettie [13] which works in general graphs. However, in comparison to their rather involved algorithm, our algorithm is simple and only uses elementary data structures. Furthermore, we are able to use properties of the algorithm to support two dynamic operations, namely one where vertices are deleted from one side and one where vertices of the other side of the bipartite graph are inserted together with their incident edges. No algorithm that allows both these operations with running time faster than recomputation from scratch was known prior.

1.1 Dynamic matching algorithms

Dynamic weighted matching. There has been a large body of work on dynamic matching and many variants of the problem have been studied, e.g, the maximum, maximal, as well as $\alpha$-approximate setting for a variety of values of $\alpha$, both in the weighted as well as in the unweighted setting. See [15] for a survey of the current state of the art for the fully dynamic setting. For any constant $\delta >0$ there is a conditional lower bound based on the OMv conjecture that shows that any dynamic algorithm that returns the exact value of a maximum cardinality matching in a bipartite graph with polynomial preprocessing time cannot take time $O(m^{1-\delta })$ per query and $O(m^{1/2 - \delta })$ per edge update operation [16].

Dynamic $(1-\varepsilon )$-approximate matchings For general weighted graphs Gupta and Peng [14] gave the first algorithm in the fully dynamic setting with edge insertions and deletions to maintain a $(1-\varepsilon )$-approximate matching in $O(\varepsilon ^{-1}\sqrt{m} \log w_{max})$ time, where the edges fall into the range $[1,w_{max}]$. There are also some results for bipartite graphs in partially dynamic settings. In the incremental setting, edges are only inserted, and decremental setting, edges are only deleted. For unweighted bipartite graphs, the fastest known decremental algorithm is by Bernstein, Probst Gutenberg, and Saranurak [4] achieves update times of $O(\varepsilon ^{-4}\log ^3(n))$ per edge deletion. For incremental algorithms Blikstad and Kiss [8] achieve update times of $O(\varepsilon ^{-6})$ time per edge insertion. These results can be made to work in weighted graphs by a meta theorem of Bernstein, Dudeja, and Langley [5]. Their theorem states that any dynamic algorithm on an unweighted bipartite graph can be transformed into a dynamic algorithm on weighted bipartite graph at the expense of an extra $(1/\varepsilon )^{O(1/\varepsilon )}\log n$ factor.

Vertex updates. By vertex update we refer to updates that are vertex insertion (resp. deletion) that also inserts (resp. deletes) all edges incident to the vertex. There is no prior work on maintaining matchings in weighted graphs under vertex updates. However, vertex updates in the unweighted bipartite setting has been studied. Bosek et al. [9] gave an algorithm that maintains the $(1-\varepsilon )$-approximate matching when vertices of one side are deleted in $O(\varepsilon ^{-1})$ amortized time per changed edge. The algorithm can be adjusted to the setting where vertices of one side are inserted in the same running time, but it cannot handle both vertex insertions and deletions. Le et al. [19] gave an algorithm for maintaining a maximal matching under vertex updates in constant amortized time per changed edge. They also presented an $e/(e-1) \approx 1.58$ approximate algorithm for maximum matchings in an unweighted graph when vertex updates are only allowed on one side of a bipartite graph.

We give the first algorithm to maintain a $(1-\varepsilon )$-approximate maximum weight matching where vertices can undergo vertex deletions on one side and vertex insertions on the other side in total time $O(m\varepsilon ^{-1})$, where m is the sum of the number of initially existing and inserted edges. It assumes that the edges incident to an inserted vertex are given in sorted order by weight, otherwise, the running time increases by $O(\log n)$ per inserted edge.

1.2 Linear program for MWM

The MWM problem can be expressed as the following linear program (LP) where the variable $x_{uv}$ denotes whether the edge uv is in the matching. It is well known [23] that the below LP is integral, that is the optimal solution has all variables $x_{uv}\in \{0, 1\}$.

$$\begin{aligned} \max \quad&\sum _{uv\in E} w(uv) x_{uv}&\\ s.t. \quad&\sum _{v \in N(u)} x_{uv} \le 1&\forall u\in U \\&\sum _{u \in N(v)} x_{uv} \le 1&\forall v\in V \\&x_{uv} \ge 0&\forall uv \in E \end{aligned}$$

We can also consider the dual problem of weighted vertex cover that aims to find dual weights $y_u$ and $y_v$ for every vertex $u\in U$ and $v\in V$ respectively.

$$\begin{aligned} \min \quad&\sum _{u\in U} y_u + \sum _{v\in V} y_v&\\ s.t.\quad&y_u + y_v \ge w(uv)&\forall uv \in E \\&y_u \ge 0&\forall u \in U \\&y_v \ge 0&\forall v \in V \end{aligned}$$

1.3 Multiplicative weight updates for packing LPs

Packing LPs are LPs of the form $\max \{c^{T}x \mid Ax \le b\}$ for $c\in \mathbb {R}^{n}_{\ge 0}$, $b\in \mathbb {R}^{m}_{\ge 0}$ and $A\in \mathbb {R}^{n\times m}_{\ge 0}$. The LP for MWM is a classical example of a packing LP. The multiplicative weight update method (MWU) has been investigated extensively to provide faster algorithms for finding approximate solutions¹ to packing LPs [1, 10, 17, 22, 24, 25]. Typically the running times for solving these LPs have a dependence on $\varepsilon$ of $\varepsilon ^{-2}$, e.g. the algorithm of Koufogiannakis and Young [17] would obtain a running time of $O(m\varepsilon ^{-2}\log n)$ when applied to the matching LP.

The fastest multiplicative weight update algorithm for solving packing LPs by Allen-Zhu and Orecchia [1] would obtain an $O(m\varepsilon ^{-1}\log n)$ running time for MWM. Very recently, work by Battacharya, Kiss, and Saranurak [7] extended the MWU for packing LPs to the partially dynamic setting. When restricted to the MWM problem means the weight of edges either only increase or only decrease. Using similar ideas with MWUs, Assadi [2] recently derived a simple semi-streaming algorithm for bipartite matchings. However as packing LPs are more general than MWM, these algorithms are significantly more complicated and are slower by $\log n$ factors (and sometimes worse dependence on $\varepsilon$ e.g. in [7]) when compared to our algorithms.

We remark that our algorithm, while it uses multiplicative weight updates, is unlike typical MWU algorithms as it has an additional monotonicity property. We only increase dual variables on one side of the matching.

1.4 Auction algorithms

Auction algorithms are a class of primal dual algorithms for solving the MWM problem that view U as a set of goods to be sold, V as a set of buyers. The goal of the auction algorithm is to find a welfare-maximizing allocation of goods to buyers. The algorithm is attributed to Bertsekas [6], as well as to Demange, Gale, and Sotomayor [12].

An auction algorithm initializes the prices of all the goods $u\in U$ with a price $y_u = 0$ (our choice of $y_u$ is intentional, as prices correspond directly to dual variables), and has buyers initially unallocated. For each buyer $v\in V$, the utility of that buyer upon being allocated $u\in U$ is ${{\,\textrm{util}\,}}(uv) = w(uv) - y_u$. The auction algorithm proceeds by asking an unallocated buyer $v \in V$ for the good they desire that maximizes their utility, i.e. for $u_v = \arg \max _{u\in N(v)} {{\,\textrm{util}\,}}(uv)$. If ${{\,\textrm{util}\,}}(u_v v) < 0$, the buyer remains unallocated. Otherwise the algorithm allocates $u_v$ to v, then increases the price $y_u$ to $y_u + \varepsilon$. The algorithm terminates when all buyers are either allocated or for every unallocated buyer v, it holds that ${{\,\textrm{util}\,}}(u_v v) < 0$. If the maximum weight among all the edges is $w_{max}$, then the auction algorithm terminates after $O(n\varepsilon ^{-1}w_{max})$ rounds and outputs a matching that differs from the optimal by an additive factor of at most $n\varepsilon$.

There have been a recent resurgence in interest in auction algorithms. Assadi, Liu, and Tarjan [3] used the auction algorithm for matchings in unweighted graphs in semi-streaming and massively parallel computing (MPC) settings. This work was generalized for weighted bipartite graphs in the same settings by Liu, Ke, and Kholler [20].

1.5 Our contribution

We present the following modification of the auction algorithm:

$$\begin{aligned} \textit{When}\, v\,\textit{is allocated }\,u,\,\textit{ increase}\,y_u\,\textit{ to}\, y_u + \varepsilon \cdot w(uv)\, \textit{instead of}\, y_u + \varepsilon . \end{aligned}$$

Note that this decreases ${{\,\textrm{util}\,}}(v)$ by at least a factor of $(1-\varepsilon )$ as well as increases $y_u$ by at least a factor of $(1+\varepsilon )$. Thus we will call algorithms with this modification multiplicative auction algorithms. Surprisingly, we were not able to find any literature on this simple modification. Changing the constant additive weight update to a multiplicative weight update has the effect of taking much larger steps when the weights are large, and so we are able to show that the algorithm can have no dependence on the size of the weights. In fact, we are able to improve the running time to $O(m\varepsilon ^{-1})$, faster than the prior approximate matching algorithm of Duan and Pettie [13] that ran in $O(m\varepsilon ^{-1}\log \varepsilon ^{-1})$. While the algorithm of [13] has the advantage that it works for general graphs and ours is limited to bipartite graphs, our algorithm is simpler as it avoids the scaling algorithm framework and is easier to implement.

Theorem 1.1

Let $G=(U\cup V, E)$ be a weighted biparitite graph and $\varepsilon$ be a value such that $1>\varepsilon >0$. There is a multiplicative auction algorithm running in time $O(m\varepsilon ^{-1})$ that finds a $(1-\varepsilon )$-approximate maximum weight matching of G.

Furthermore, it is straightforward to extend our algorithm to a setting where vertices on one side are deleted and vertices on the other side are added with all incident edges given in sorted order of weight. When the inserted edges are not sorted by weight, the running time per inserted edge increases by an additive term of $O(\log \log n)$ to sort the log of the weights of all incident inserted edges.

Theorem 1.2

Let $G=(U\cup V, E)$ be a weighted bipartite graph. There exists a dynamic data structure that maintains a $(1-\varepsilon )$-approximate maximum weight matching of G and supports any arbitrary sequence of the following operations

• (1) Deleting a vertex in U

• (2) Adding a new vertex into V with all its incident edges sorted by weight

in total time $O(m\varepsilon ^{-1})$, where m is sum of the number of initially existing and inserted edges.

2 The static algorithm

2.1 A slower algorithm

For sake of exposition we will first present a slower algorithm that runs in near-linear time in the number of edges that will use the following update rule:

$$\begin{aligned} \textit{ When}\, u\,\textit{ is allocated to}\, v,\,\textit{ increase}\, y_u\,\textit{ to}\, y_u + \varepsilon \cdot {{\,\textrm{util}\,}}(uv) \end{aligned}$$

We assume that the algorithm is given as input some fixed $0<\varepsilon '<1$, and the goal is to find a $(1-\varepsilon ')$-approximate MWM. We will also assume that $m= \Omega (n)$, as a graph with m edges has at most 2m vertices that have at least one incident edge. If $2m < n$, then we may discard the isolated vertices and reduce n.

Notation For sake of notation let $N(u) = \{v\in V \mid uv \in E\}$ be the set of neighbors of $u\in U$ in G, and similarly for N(v) for $v\in V$.

Preprocessing of the weights. Let $w_{max} > 0$ be the maximum weight edge of E. For our static auction algorithm we may ignore any edge $uv \in E$ of weight less than $\varepsilon '\cdot w_{max}/n$ as $w(M^*) \ge w_{max}$ as taking n of these small weight edges would not even contribute $\varepsilon '\cdot w(M^*)$ to the matching. Thus, we only consider edges of weight at least $\varepsilon '\cdot w_{max}/n$, which allows us to rescale all edge weights by dividing them by $\varepsilon '\cdot w_{max}/n$. As a result we can assume (by slight abuse of notation) in the following that the minimum edge weight is 1 and the largest edge weight $w_{max}$ equals $n/\varepsilon '$. Furthermore, since we only care about approximations, we will also round down all edge weights to the nearest power of $(1+\varepsilon )$ for some $\varepsilon < \varepsilon '/2$. We define $\textsc {iLog}(x) = \lfloor \log _{1+\varepsilon } (x) \rfloor$, and we will only care about weights after applying this operation.

Let $k_{max} = \textsc {iLog}(w_{max}) = \textsc {iLog}(n/\varepsilon ') = O(\varepsilon ^{-1} \log (n/\varepsilon ))$. Let $k_{min}$ be the smallest integer such that $(1+\varepsilon )^{-k_{min}} \le \varepsilon$. Observe that as $\log (1 +\varepsilon ) \le \varepsilon$ for $0 \le \varepsilon \le 1$ it holds that

$$\begin{aligned} k_{min} \ge \frac{\log (\varepsilon ^{-1})}{\log (1+\varepsilon )} \ge \varepsilon ^{-1} \log (\varepsilon ^{-1}). \end{aligned}$$

Thus we see that $k_{min} = \Theta (\varepsilon ^{-1}\log (\varepsilon ^{-1}))$.

Algorithm. The algorithm first builds for every $v \in V$ a list $Q_v$ of pairs (i, uv) for each edge uv and each value i with $-k_{min} \le i \le j_{uv} = \textsc {iLog}(w_{uv})$ and then sorts $Q_v$ by decreasing value of i. After, it calls the function $\textsc {MatchR}(v)$ on every $v \in V$. The function $\textsc {MatchR}(v)$ matches v to the item that maximizes its utility and updates the price $y_u$ according to our multiplicative update rule. While matching v, another vertex $v'$ originally matched to v may become unmatched. If this happens, $\textsc {MatchR}(v')$ is called immediately after $\textsc {MatchR}(v)$.

Data structure. We store for each vertex $v \in V$ the list $Q_v$ as well as its currently matched edge if it exists. In the pseudocode we keep for each vertex v a value $j_v$ corresponding to the highest weight threshold $(1+\varepsilon )^{j_v}$ that we will consider. We also keep a value $y_v$ which corresponds to the utility v receives before we update the price $y_u$ when v is matched to u. Note that $j_v$ and $y_v$ are only needed in the analysis.

Running time. The creation and sorting of the lists $Q_v$ takes time $O(|N(v)|(k_{max} + k_{min}))$ if we use bucket sort as there are only $k_{max} + k_{min}$ distinct weights. The running time of all calls to $\textsc {MatchR}(v)$ is dominated by the size of $Q_v$, as each iteration in $\textsc {MatchR}(v)$ removes an element of $Q_v$ and takes O(1) time. Thus, the total time is $O\left( \sum _{v\in V} |N(v)|(k_{max} + k_{min})\right) = O(m(k_{max} + k_{min})) = O(m\varepsilon ^{-1} \log (n/\varepsilon )).$

Invariants maintained by the algorithm. The algorithm maintains five different invariants.

Invariant 1

For all $v\in V$, and all $u\in N(v)$, ${{\,\textrm{util}\,}}(uv)= w(uv) - y_u \le (1+\varepsilon )^{j_v+1}$.

Proof

This clearly is true at the beginning, since $j_v$ is initialized to $k_{max}$, and

$$\begin{aligned} {{\,\textrm{util}\,}}(uv) = w(uv) < (1+\varepsilon )^{j_{uv}+1}. \end{aligned}$$

As the algorithm proceeds, ${{\,\textrm{util}\,}}(uv)$ which equals $w(uv) - y_u$ only decreases as $y_u$ only increases. Thus, we only have to make sure that the condition holds whenever $j_v$ decreases. The value $j_v$ only decreases from some value, say $j+1$, to a new value j, in MatchR(v) and when this happens $Q_v$ does not contain any pairs $(j',uv)$ with $j' >j$ anymore. Thus, there does not exist a neighbor u of v with ${{\,\textrm{util}\,}}(uv) \ge (1+\varepsilon )^{j+1}$. It follows that when $j_v$ decreases to j for all $u \in N(v)$ it holds that ${{\,\textrm{util}\,}}(uv) < (1+\varepsilon )^{j_v+1}$. $\square$

Invariant 2

For all $u\in U$ $y_u\ge 0$ and $y_u$ never decreases over the course of the algorithm. Furthermore, if $u\in U$ is not matched, then $y_u = 0$.

Proof

We initialize $y_u$ to 0. If u is never matched, we never change $y_u$, so it stays 0. Throughout the algorithm, we only ever increase $y_u$. $\square$

Invariant 3

For all $v\in V$ for which MatchR(v) was called at least once, if v is unmatched, then $y_v=0$ and $Q_v$ is empty. Furthermore, for all $u\in N(v)$ we have that $y_u + y_v = y_u > (1-\varepsilon ) \cdot w(uv)$.

Proof

MatchR(v) terminates (i) after it matches v and recurses or (ii) if $Q_v$ is empty. Initially v is unmatched and $y_v$ is set to 0. If v is matched, it is possible that for some $v'\in V$, $v' \ne v$, that v becomes temporarily unmatched during MatchR$(v')$ and $y_v$ is set to 0, but MatchR(v) will be immediately called again. Thus, whenever v is unmatched, $y_v = 0$.

Hence, if the last call to MatchR(v) does not result in v being matched, then this means that $Q_v$ must be empty and $y_v = 0$. Since $Q_v$ is empty, then for all $u\in N(v)$, we must have ${{\,\textrm{util}\,}}(uv) < (1+\varepsilon )^{-k_{min}} \le \varepsilon$. Since we rescaled weights so that $w(uv) \ge 1$, we know that ${{\,\textrm{util}\,}}(uv) < \varepsilon \le \varepsilon \cdot w(uv)$. Note that ${{\,\textrm{util}\,}}(uv) = w(uv) -y_u^*$ where $y_u^*$ denotes the value of $y_u$ before u was matched, and $y_u \ge y_u^*$. Thus,

$$\begin{aligned} y_u \ge y_u^* = w(uv) - {{\,\textrm{util}\,}}(uv) > (1-\varepsilon ) \cdot w(uv). \end{aligned}$$

$\square$

Invariant 4

If $v\in V$ is matched to $u\in U$, then for all $u' \in N(v)$, $y_{u'} + y_{v} \ge (1-\varepsilon )\cdot w(u'v)$ for as long as v stays matched.

Proof

Note that $y_v$ doesn’t change as long as v stays matched, and for all $u'\in N(v)$, $y_{u'}$ can only increase by Invariant 2, so it suffices to prove $y_{u'} + y_{v} \ge (1-\varepsilon )\cdot w(u'v)$ right after v was matched to u.

Let $y_u^*$ be the value of $y_u$ right before v was matched to u. Note that $y_v = w(uv) - y_u^*$. For $u' = u$, we know that $y_v + y_u^* = w(uv)$, and, by Invariant 2, $y_{u}^* \le y_u$ so $y_v + y_u \ge w(uv)$.

For all other $u' \in U$, right before we updated $y_u$, we had that $(1+\varepsilon )^{j_v}\le {{\,\textrm{util}\,}}(uv)$ and, by Invariant 1, ${{\,\textrm{util}\,}}(u'v) \le (1+\varepsilon )^{j_v+1}$. Thus, $(1+\varepsilon ) \cdot {{\,\textrm{util}\,}}(uv) \ge {{\,\textrm{util}\,}}(u'v)$, so that ${{\,\textrm{util}\,}}(uv) = w(uv) - y^*_u = y_v \ge (1+\varepsilon )^{-1} \cdot (w(u'v) - y_{u'})$. As $y_{u'}\ge 0$ by Invariant 2, it follows that:

$$\begin{aligned} y_{v} + y_{u'} \ge (1+\varepsilon )^{-1} \cdot w(u'v) + (1 - (1+\varepsilon )^{-1}) \cdot y_{u'} \ge (1-\varepsilon ) \cdot w(u'v), \end{aligned}$$

as $1> \varepsilon > 0$. $\square$

Invariant 5

If $v\in V$ is matched to $u\in U$, then $y_u + y_v \le (1+\varepsilon )\cdot w(uv)$ for as long as v remains matched to u.

Proof

Note that $y_u$ and $y_v$ don’t change as long as v remains matched to u. Let $y_u^*$ denote the value of $y_u$ right before the update rule of line 5(b) in MatchR. Then observe $y_u = y_u^* + \varepsilon \cdot (w(uv) - y_u^*)$, and $y_v = w(uv) - y_u^*$. Thus,

$$\begin{aligned} y_u + y_v&= y_u^* + \varepsilon \cdot (w(uv) - y_u^*) + w(uv) - y_u^*\\&= (1+\varepsilon ) \cdot w(uv) - \varepsilon \cdot y_u^*\\&\le (1+\varepsilon ) \cdot w(uv). \end{aligned}$$

$\square$

Approximation factor. We will show the approximation factor of the matching M found by the algorithm by primal dual analysis. We remark that it is possible to show this result purely combinatorially as well. We will show that this M and a vector y satisfy the complementary slackness condition up to a $1\pm \varepsilon$ factor, which implies the approximation guarantee. This was used by Duan and Pettie [13] (the original lemma was for general matchings, we have specialized it here to bipartite matchings).

Lemma 2.1

(Lemma 2.3 of [13]) Let M be a matching and let y be an assignment of the dual variables. Suppose y is a complementary solution to M in the following approximate sense:

• (i) For all $uv \in E, y_u + y_v \ge (1-\varepsilon _0) \cdot w(uv)$,

• (ii) For all $e\in M$, $y_u+y_v \le (1+\varepsilon _1) \cdot w(uv)$,

• (iii) The y-values of all unmatched vertices are zero.

Then M is a $\left( (1+\varepsilon _1)^{-1}(1-\varepsilon _0)\right)$-approximate maximum weight matching.

Proof

Let $M^*$ be the maximum weight matching.

$$\begin{aligned} w(M)&= \sum _{uv\in M} w(uv){} & {} \\&\ge \sum _{uv\in M}(1+\varepsilon _1)^{-1} \cdot (y_u+y_v){} & {} \text {by (ii)}\\&= (1+\varepsilon _1)^{-1} \left( \sum _{u\in U} y_u+\sum _{v\in V}y_v\right){} & {} \text {by (iii)}\\&\ge (1+\varepsilon _1)^{-1} \sum _{uv\in M^*} (y_u + y_v){} & {} \text {as}\, M^*\,\text {is a matching}\\&\ge (1+\varepsilon _1)^{-1} \sum _{uv\in M^*} (1-\varepsilon _0) \cdot w(uv){} & {} \text {by (i)}\\&\ge (1-\varepsilon _0)(1+\varepsilon _1)^{-1} w(M^*){} & {} \end{aligned}$$

$\square$

This lemma along with our invariants is enough for us to prove the approximation factor of our algorithm.

Lemma 2.2

MultiplicativeAuction$(G = (U\cup V, E))$ outputs a $(1-\varepsilon ')$-approximate maximum weight matching of the bipartite graph G.

Proof

Let $\varepsilon > 0$ be a parameter depending on $\varepsilon '$ that we will choose later. We begin by choosing an assignment of the dual variables $y_u$ for $u \in U$ and $y_v$ for $v \in V$ as exactly the values used by the algorithm at termination. It remains to verify that we satisfy the conditions of Lemma 2.1. Property (i) is satisfied by Invariant 3 or Invariant 4 (depending on whether v is matched or not) for $\varepsilon _0 = \varepsilon$. Property (ii) is satisfied by Invariant 5 for $\varepsilon _1 = \varepsilon$. Property (iii) is satisfied by Invariant 2 and Invariant 3. Thus we have satisfied Lemma 2.1 with $\varepsilon _0 = \varepsilon$ and $\varepsilon _1 = \varepsilon$. Setting $\varepsilon = \varepsilon '/2$ gives us a $(1-\varepsilon ')$-approximate maximum weight matching. $\square$

We have shown the following result that is weaker than what we have set out to prove by a factor of $\log (n\varepsilon ^{-1})$ that we will show how to get rid of in Sect. 2.2.

Theorem 2.1

Let $G=(U\cup V, E)$ be a weighted biparitite graph, and $\varepsilon$ be a value such that $1>\varepsilon > 0$. There exists a multiplicative auction algorithm running in time $O(m\varepsilon ^{-1}\log (n\varepsilon ^{-1}))$ that finds a $(1-\varepsilon )$-approximate maximum weight matching of G.

2.2 Improving the running time

Variations to the update rule We remark that there is some flexibility in choosing the update rule in line 5(a) of MatchR.

Observation 2.1

To compute an $(1-\varepsilon ')$-approximate maximum weight matching the update rule in line 5(a) of MatchR can be any of the following:

• (1) $y_u\leftarrow y_u + \delta \cdot ({{\,\textrm{util}\,}}(uv))$, with $\delta \le \varepsilon '/2$,

• (2) $y_u\leftarrow y_u+ \delta \cdot (y_u)$, with $\delta \le \varepsilon '/2$,

• (3) $y_u\leftarrow y_u + \delta \cdot (w(uv))$, with $\delta \le \varepsilon '/4$.

Proof

It suffices to verify that all invariants hold for different update rules. Invariant 1, 2, 3, and 4 all hold regardless of the update rule, as they only use the fact that $y_u$ is non-decreasing throughout the algorithm, so we will only focus on Invariant 5.

We proved that update rule (1) works in Sect. 2.1 for $\delta = \varepsilon = \varepsilon '/2$. Note that if we chose an $\delta < \varepsilon$, we would still have $y_u \le y_u^* + \varepsilon (w(uv)-y_u^*)$, and Invariant 5 holds.

To prove update rule (2) works for $\delta \le \varepsilon = \varepsilon '/2$, let $v\in V$ be matched to $u\in U$, and $y_u^*$ be the value of $y_u$ right before the update rule. Observe that $y_u = (1+\delta )\cdot y_u^* \le (1+\varepsilon )\cdot y_u^*$ and $y_v = w(uv)-y_u^*$. Furthermore $y_u^* \le w(uv)$ as otherwise ${{\,\textrm{util}\,}}(uv) < 0$ and v would not be trying to match to u. Thus,

$$\begin{aligned} y_u + y_v \le (1+\varepsilon )\cdot y_u^* + w(uv) - y_u^* = w(uv) + \varepsilon \cdot y_u^* \le (1+\varepsilon )\cdot w(uv). \end{aligned}$$

Since we have shown that either update rule (1) or (2) work, we can choose the larger of the two update rules, i.e. the update of adding $\delta \cdot \max \{util(uv), y_u\}$ is also a valid update rule. However, as ${{\,\textrm{util}\,}}(uv) + y_u = w(uv)$, this means that $\delta \cdot (w(uv)) \le \varepsilon '/4 \cdot (w(uv))$, so (3) is also a valid update rule.

Remarks. Update rule (2) offers an alternative way to implement the algorithm with a running time of $O(m\varepsilon ^{-1}\log (n\varepsilon ^{-1})$. Update rule (3) shows that v can update the value of $y_u$ at most $O(\varepsilon ^{-1})$ times before ${{\,\textrm{util}\,}}(uv)$ becomes non-positive, so using update rule (3) results in at most $O(m\varepsilon ^{-1})$ total updates. Furthermore, a careful reader may have noticed that Invariant 3 only requires for an edge uv that ${{\,\textrm{util}\,}}(uv)\le \varepsilon \cdot w(uv)$ when we stop considering that edge, so it suffices to only consider edges in multiples of $\varepsilon /2$ and stop considering an edge when it falls below a value of $\varepsilon \cdot w(uv)$.

Improved algorithm For simplicity of the exposition we will assume $2\varepsilon ^{-1}$ is a positive integer (otherwise we can choose a slightly smaller $\varepsilon$). To improve the running time to $O(m\varepsilon ^{-1})$, we use the observation in the above remark that every edge only needs to be updated $O(\varepsilon ^{-1})$ times if we use update rule (3) and we only need to consider edges in multiples of $\varepsilon /2$. Thus it suffices if we change line 1.(b) in MultiplicativeAuction to insert copies of an edge uv if it has weight of the form $j \cdot w(uv)$ for some $j=\varepsilon , 3\varepsilon /2, 2\varepsilon , \dots , 1$, after rounding down to the nearest power of $(1+\varepsilon )$. This change implies that we insert $O(\varepsilon ^{-1} |N(v)|)$ items into $Q_v$ for every $v\in V$. However, sorting $Q_v$ for every vertex individually, would be too slow.

We will instead sort on all the rounded edge weights at once, as we have $O(m\varepsilon ^{-1} )$ total copies of the edges that can take on values of integers between $-k_{min}$ and $k_{max}$. As $k_{max}+k_{min} = O(n\varepsilon ^{-1}\log \varepsilon ^{-1}) = {{\,\textrm{poly}\,}}(n)$, we can actually use radix sort to sort all the edges in linear time. Afterwards, we can go through the weight classes in decreasing order to insert the pairs into the corresponding $Q_v$. We explicitly give the pseudocode below as MultiplicativeAuction+.

New runtime. Radix sorting all $O(m\varepsilon ^{-1})$ pairs and initializing the sorted $Q_v$ for all $v\in V$ takes linear time in the number of pairs. The total amount of work done in MatchR(v) for a vertex $v\in V$ is $O(|N(v)| \varepsilon ^{-1})$ which also sums to $O(m \varepsilon ^{-1})$. Thus we get our desired running time and have proven our main theorem that we restate here.

Theorem 1.1

Let $G=(U\cup V, E)$ be a weighted biparitite graph and $\varepsilon$ be a value such that $1>\varepsilon >0$. There is a multiplicative auction algorithm running in time $O(m\varepsilon ^{-1})$ that finds a $(1-\varepsilon )$-approximate maximum weight matching of G.

3 Dynamic algorithm

There are many monotonic properties of our static algorithm. For instance, for all $u\in U$ the $y_u$ values strictly increase. As another example, for all $v\in V$ the value of $j_v$ strictly decreases. These monotonic properties allow us to extend MultiplicativeAuction+ to a dynamic setting with the following operations.

Theorem 1.2

Let $G=(U\cup V, E)$ be a weighted bipartite graph. There exists a dynamic data structure that maintains a $(1-\varepsilon )$-approximate maximum weight matching of G and supports any arbitrary sequence of the following operations

• (1) Deleting a vertex in U

• (2) Adding a new vertex into V with all its incident edges sorted by weight

in total time $O(m\varepsilon ^{-1})$, where m is sum of the number of initially existing and inserted edges.

Type (1) operations: Deleting a vertex in U. To delete a vertex $u\in U$, we can mark u as deleted and skip all edges uv in $Q_v$ for any $v\in V$ in all further computation. If u were matched to some vertex $v\in V$, that is if there exists an edge $uv \in M$, we need to unmatch v and remove uv from M. All our invariants hold except Invariant 3 for the unmatched v. To restore this invariant we simply call MatchR(v).

Type (2) operations: Adding a new vertex to V with all incident edges. To add a new vertex v to V with $\ell$ incident edges to $u_1v, \dots , u_\ell v$ with $w(u_1v)> \cdots > w(u_\ell v)$, we can create the queue $Q_v$ by inserting the $O(\varepsilon ^{-1})$ pairs such that it is non-increasing in the first element of the pair. Afterwards we call MatchR(v). All invariants hold after doing so.