Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs

We write [n] for the interval 1, 2, ..., n. For a set I ⊂ [n] we also use I as 0/1-vector with I i = 1 when i ∈ I and I i = 0 otherwise. We write e i for the i-th standard unit vector. We use O(•) notation to hide (log log W ) O(1) and (log n) O(1) factors, where W typically denotes the largest absolute value used for specifying any value in the problem (e.g. demands and edge weights) and n denotes the number of nodes.

When we write with high probability (or w.h.p), we mean with probability 1 -n c for any constant c > 0.

For x ∈ R n , we use x i to denote the i-th coordinate of vector x if the symbol x is simple. If the symbol is complicated, we use (x) i or [x] i to denote the i-th coordinate of vector x (e.g. (δ s ) i ).

We write 1 condition for the indicator variable, which is 1 if the condition is true and 0 otherwise.

Given a vector v ∈ R d for some d, we write Diag(v) for the d×d diagonal matrix with Diag(v) i,i = v i . For vectors x, s, s, x, x t , s t , w, w, w t , τ, g we let X def = Diag(x), S def = Diag(s), and define X, S, X t , S t , W, W, W t , T, G analogously.

Given vectors u, v ∈ R d for some d, we perform arithmetic operations •, +, -, /, √ • element-wise. For example (u•v

For the inner product we will write u, v and u v instead. For a vector v ∈ R d and a scalar α ∈ R we have (αv) i = αv i and we extend this notation to other arithmetic operations, e.g.

For symmetric matrices A, B ∈ R n×n we write A B to indicate that x Ax ≤ x Bx for all x ∈ R n and define , ≺, and analogously. We let S n×n >0 ⊆ R n×n denote the set of n × n symmetric positive definite matrices. We call any matrix (not necessarily symmetric) non-degenerate if its rows are all non-zero and it has full column rank.

We use a ≈ b to denote that exp(-)b ≤ a ≤ exp( )b entrywise and A ≈ B to denote that exp(-)B A exp( )B. Note that this notation implies a ≈ b ≈ δ c ⇒ a ≈ +δ c, and a ≈ b ⇒ a x ≈ •x b x for x ≥ 0.

For any matrix A over reals, let nnz(A) denote the number of non-zero entries in A.