?. , Since v ? B, the onus of maintaining the set F v (S) falls squarely upon the nodes in N (v, H S ) ? S. Specifically, each small node u ? S maintains a "status-bit" indicating if it is free or not. Whenever a matched small node u changes its status-bit, it communicates this information to its neighbors in N (u, H S ) ? B in O(deg(u, H S )) = O(log 2 n) time. Using the lists {F v (S)}, v ? B, and the status-bits of the small nodes, after each edge insertion/deletion in H S , we can update the maximal b-matching M S in O(log 2 n) worst case time, with high probability, v) is inserted into/deleted from the set E * only when its weight w(e) is changed. Thus, maintaining the linked list for E * does not incur any additional overhead in the update time. Next, we show to maintain the edge-set H S by independently sampling each edge e ? E S with probability p e. This probability is completely determined by the weight w(e), vol.40, p.41

, We store the ordered sequence of |B| numbers a 1 (v),. .. , a |B| (v) in the leaves of a balanced binary tree from left to right. Let x i denote the leaf node that stores the value a i (v). Further, at each internal node x of the balanced binary tree, we store the sum S x = i:x i ?T (x) a i (v), where T (x) denotes the set of nodes in the subtree rooted at x. This data structure can support the following operations. INCREMENT(i, ?): This asks us to set a i (v) ? a i (v) + ?, where ? is any real number. To perform this update, we first change the value stored at the leaf node x i. Then starting from the node x i , we traverse up to the root of the tree. At each internal node x in this path from x i to the root, we set S x ? S x + ?. The S x values at every other internal node remains unchanged, We maintain the sums {A i (v)}, i, and the set N (v, H B ) using a balanced binary tree data structure, as described below

. Return-index-;-?-y-&lt;-c-v, We can answer this query in O(log n) time by doing binary search. Specifically, we perform the following operations. We initialize a counter C ? 0 and start our binary search at the root of the tree. At an intermediate stage of the binary search, we are at some internal node x and we know that y < C + S x. Let x(l) and x(r) respectively be the left and right child of x

. If-y-&lt;-c-+-s-x, We use the above data structure to maintain the sets N (v, H B ), v ? S. Whenever the weight of an edge (u, v), v ? S, changes, we can update the set N (v, H B ) by making one call to the INCREMENT(i, ?), and c v calls to RETURN-INDEX(y), one for each y = k + ? v , where k < c v is a nonnegative integer, Otherwise, we set C ? C + S x(l) and move to the node x(r)

, Applying this framework, we obtained the first nontrivial dynamic algorithms for the set cover and b-matching problems. Specifically, we presented a dynamic algorithm for set cover that maintains a O(f 2 )-approximation in O(f · log(m + n)) update time, where f is the maximum frequency of an element, m is the number of sets and n is the number of elements

, log n))-approximation in O(f · (m + n))-time. Can we match this approximation guarantee in the dynamic setting in O(f · poly log(m + n)) update time? As a first step, it will be interesting to design a dynamic algorithm for fractional hypergraph b-matching that maintains a O(f )-approximation and has an update time of O

, Are there other well known problems (such as facility location, Steiner tree etc.) that can be solved in the dynamic setting using the primal-dual framework?

K. J. Ahn and S. Guha, Near linear time approximation schemes for uncapacitated and capacitated b-matching problems in nonbipartite graphs, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.239-258, 2014.

R. Bar-yehuda and S. Even, A linear time approximation algorithm for the weighted vertex cover problem, Journal of Algorithms, vol.2, pp.198-203, 1981.

S. Baswana, M. Gupta, and S. Sen, Fully dynamic maximal matching in O(log n) update time, 52nd IEEE Symposium on Foundations of Computer Science, pp.383-392, 2011.

S. Bhattacharya, M. Henzinger, and G. F. Italiano, Deterministic fully dynamic data structures for vertex cover and matching, Procs. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pp.785-804, 2015.

N. Buchbinder and J. Naor, The design of competitive online algorithms via a primal-dual approach, Foundations and Trends in Theoretical Computer Science, vol.3, issue.2-3, pp.93-263, 2009.

G. B. Dantzig, L. R. Ford, and D. R. Fulkerson, A primal-dual algorithm for linear programs, Linear Inequalities and Related Systems, pp.171-181, 1956.

D. Eppstein, Z. Galil, and G. F. Italiano, Dynamic graph algorithms, Algorithms and Theory of Computation Handbook, vol.1, pp.9-10, 2009.

U. Feige, A threshold of ln n for approximating set cover, Journal of the ACM, vol.45, pp.634-652, 1998.

H. N. Gabow, An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp.25-27

M. Goemans and D. P. Williamson, A general approximation technique for constrained forest problems, SIAM J. Comput, vol.24, pp.296-317, 1992.

M. X. Goemans and D. P. Williamson, The primal-dual method for approximation algorithms and its application to network design problems, Approximation algorithms for NP-hard problems, pp.144-191, 1997.

M. Gupta and R. Peng, Fully dynamic (1 + ?)-approximate matchings, 54th IEEE Symposium on Foundations of Computer Science, pp.548-557, 2013.
DOI : 10.1109/focs.2013.65

D. S. Johnson, Approximation algorithms for combinatorial problems, Journal of Computer and System Sciences, vol.9, pp.256-278, 1974.

S. Khot and O. Regev, Vertex cover might be hard to approximate to within 2? ?, Journal of Computer and System Sciences, vol.74, 2008.

S. Korman, On the Use of Randomization in the Online Set Cover Problem. Weizmann Institute of Science, 2004.

H. W. Kuhn, The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, vol.2, pp.83-97, 1955.

O. Neiman and S. Solomon, Simple deterministic algorithms for fully dynamic maximal matching, 45th ACM Symposium on Theory of Computing, pp.745-754, 2013.

K. Onak and R. Rubinfeld, Maintaining a large matching and a small vertex cover, 42nd ACM Symposium on Theory of Computing, pp.457-464, 2010.

V. V. Vazirani, Approximation Algorithms, 2001.