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.


  The deal is that Payday Loans Indiana online can save your time, nerves and make a solution of all your financial problems. In rare cases, the smarting in eyes and the tumefaction of eyelids can happen. In case of long term Cialis Black administration the side effects become less perceptible or disappear at all.