## Invited Session Thu.3.H 3005

#### Thursday, 15:15 - 16:45 h, Room: H 3005

**Cluster 2: Combinatorial optimization** [...]

### Recent advances in matching algorithms

**Chair: Piotr Sankowski**

**Thursday, 15:15 - 15:40 h, Room: H 3005, Talk 1**

**Manoj Gupta**

Fully dynamic maximal matching in *O(**log* n) update time

**Coauthors: Surender Baswana, Sandeep Sen**

**Abstract:**

We present an algorithm for maintaining maximal matching in a graph under addition and deletion of edges. Our data structure is randomized that takes *O(**log* n) expected amortized time for each edge update where n is the number of vertices in the graph. While there is a trivial *O(n)* algorithm for edge update, the previous best known result for this problem for a graph with n vertices and m edges is *O({(n+ m)}*^{0.7072}) which is sub-linear only for a sparse graph.

For the related problem of maximum matching, Onak and Rubinfield designed a randomized data structure that achieves *O(**log*^{2} n) amortized time for each update for maintaining a c-approximate maximum matching for some large constant c. In contrast, we can maintain a factor two approximate maximum matching in *O(**log* n) expected time per update as a direct corollary of the maximal matching scheme. This in turn also implies a two approximate vertex cover maintenance scheme that takes *O(**log* n) expected time per update.

**Thursday, 15:45 - 16:10 h, Room: H 3005, Talk 2**

**Chien-Chung Huang**

Efficient algorithms for maximum weight matchings in general graphs with small edge weights

**Coauthor: Telikepalli Kavitha**

**Abstract:**

Let *G=(V,E)* be a graph with positive integral edge weights. Our problem is to find a matching of maximum weight in *G*. We present a simple iterative algorithm for this problem that uses a maximum cardinality matching algorithm as a subroutine. Using the current fastest maximum cardinality matching algorithms, we solve the maximum weight matching problem in *O(W√n m**log*_{n} (n^{2}/m)) time, or in *O(Wn*^{w}) time with high probability, where *n=|V|*, *m=|E|*, *W* is the largest edge weight, and *w < 2.376* is the exponent of matrix multiplication.

In relatively dense graphs, our algorithm performs better than all existing algorithms with *W= o(**log*^{1.5}n). Our technique hinges

on exploiting Edmonds' matching polytope and its dual.

**Thursday, 16:15 - 16:40 h, Room: H 3005, Talk 3**

**Mohammad Mahdian**

Online bipartite matching with random arrivals: An approach based on strongly factor-revealing LPs

**Coauthor: Qiqi Yan**

**Abstract:**

Karp, Vazirani, and Vazirani show that a simple ranking algorithm achieves a competitive ratio of *1-1/e* for the online bipartite matching problem in the standard adversarial model. Their result also implies that in the random arrivals model defined by Goel and Mehta, where the online nodes arrive in a random order, a simple greedy algorithm achieves a competitive ratio of *1-1/e*. In this paper, we study the ranking algorithm in the random arrivals model, and show that it has a competitive ratio of at least 0.696, beating the *1-1/e ~= 0.632* barrier in the adversarial model. Our analysis has two main steps. First, we exploit properties of the ranking algorithm to derive a family of factor-revealing linear programs (LPs). Second, to obtain a good lower bound on the optimal values of all these LPs and hence on the competitive ratio of the algorithm, we derive a family of modified LPs such that the optimal value of any single one of these LPs is a lower bound on the competitive ratio of the algorithm. This enables us to leverage the power of computer LP solvers to solve for large instances of the new LPs to establish bounds that would otherwise be difficult to attain by human analysis.