DocumentCode :
180794
Title :
Online Bipartite Matching in Offline Time
Author :
Bosek, Bartlomiej ; Leniowski, Dariusz ; Sankowski, Piotr ; Zych, Anna
Author_Institution :
Theor. Comput. Sci. Dept., Jagiellonian Univ., Kraków, Poland
fYear :
2014
fDate :
18-21 Oct. 2014
Firstpage :
384
Lastpage :
393
Abstract :
This paper investigates the problem of maintaining maximum size matchings in incremental bipartite graphs. In this problem a bipartite graph G between n clients and n servers is revealed online. The clients arrive in an arbitrary order and request to be matched to a subset of servers. In our model we allow the clients to switch between servers and want to maximize the matching size between them, i.e., after a client arrives we find an augmenting path from a client to a free server. Our goals in this model are twofold. First, we want to minimize the number of times clients are reallocated between the servers. Second, we want to give fast algorithms that recompute such reallocation. As for the number of changes, we propose a greedy algorithm that chooses an augmenting path π that minimizes the maximum number of times each server in π was used by augmenting paths so far. We show that in this algorithm each server has its client reassigned O(√n) times. This gives an O(n3/2) bound on the total number of changes, what gives a progress towards the main open question risen by Chaudhuri et al. (INFOCOM´09) who asked to prove O(n log n) upper bound. Next, we argue that the same bound holds in the decremental case. Moreover, we show incremental and decremental algorithms that maintain (1 - ε)-approximate matching with total of O(ε-1n) reallocations, for any ε > 0. Finally, we address the question of how to efficiently compute paths given by this greedy algorithm. We show that by introducing proper amortization we can obtain an incremental algorithm that maintains the maximum size matching in total O(√nm) time. This matches the running time of one of the fastest static maximum matching algorithms that was given by Hopcroft and Karp (SIAM J. Comput ´73). We extend our result to decremental case where we give the same total bound on the running time. Additionally, we show O(ε-1- ) time incremental and decremental algorithms that maintain (1 - ε)-approximate matching for any ε > 0. Observe that this bound matches the running time of the fastest approximate static solution as well.
Keywords :
computational complexity; graph theory; greedy algorithms; ε-1m) time decremental algorithm; (1 - ε)-approximate matching; O(ε-1m) time incremental algorithm; O(ε-1n) reallocations; O(√n) time; O(n log n) upper bound; O(n3/2) bound; amortization; approximate static solution; augmenting path; client-server system; greedy algorithm; incremental bipartite graphs; maximum size matchings; offline time; online bipartite matching; running time; static maximum matching algorithms; total O(√nm) time; Approximation algorithms; Approximation methods; Bipartite graph; Computer science; Greedy algorithms; Heuristic algorithms; Servers; algorithm; bipartite graph; incremental; matching; online;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on
Conference_Location :
Philadelphia, PA
ISSN :
0272-5428
Type :
conf
DOI :
10.1109/FOCS.2014.48
Filename :
6979023
Link To Document :
بازگشت