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


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(log2 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


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 mlogn (n2/m)) time, or in O(Wnw) 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(log1.5n). 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


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.


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.