, 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
, 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
, 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?
, 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.
DOI : 10.1137/1.9781611973402.18
URL : https://epubs.siam.org/doi/pdf/10.1137/1.9781611973402.18
, A linear time approximation algorithm for the weighted vertex cover problem, Journal of Algorithms, vol.2, pp.198-203, 1981.
DOI : 10.1016/0196-6774(81)90020-1
, Fully dynamic maximal matching in O(log n) update time, 52nd IEEE Symposium on Foundations of Computer Science, pp.383-392, 2011.
DOI : 10.1109/focs.2011.89
URL : http://arxiv.org/pdf/1103.1109
, 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.
DOI : 10.1137/1.9781611973730.54
URL : https://epubs.siam.org/doi/pdf/10.1137/1.9781611973730.54
, 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.
, A primal-dual algorithm for linear programs, Linear Inequalities and Related Systems, pp.171-181, 1956.
DOI : 10.1515/9781400881987-008
, Dynamic graph algorithms, Algorithms and Theory of Computation Handbook, vol.1, pp.9-10, 2009.
, A threshold of ln n for approximating set cover, Journal of the ACM, vol.45, pp.634-652, 1998.
, 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
DOI : 10.1145/800061.808776
, A general approximation technique for constrained forest problems, SIAM J. Comput, vol.24, pp.296-317, 1992.
DOI : 10.1137/s0097539793242618
URL : http://web.eecs.umich.edu/~pettie/matching/Goemans-Williamson-clustering-approximation-algorithms.pdf
, The primal-dual method for approximation algorithms and its application to network design problems, Approximation algorithms for NP-hard problems, pp.144-191, 1997.
, Fully dynamic (1 + ?)-approximate matchings, 54th IEEE Symposium on Foundations of Computer Science, pp.548-557, 2013.
DOI : 10.1109/focs.2013.65
, Approximation algorithms for combinatorial problems, Journal of Computer and System Sciences, vol.9, pp.256-278, 1974.
, Vertex cover might be hard to approximate to within 2? ?, Journal of Computer and System Sciences, vol.74, 2008.
, On the Use of Randomization in the Online Set Cover Problem. Weizmann Institute of Science, 2004.
, The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, vol.2, pp.83-97, 1955.
, Simple deterministic algorithms for fully dynamic maximal matching, 45th ACM Symposium on Theory of Computing, pp.745-754, 2013.
, Maintaining a large matching and a small vertex cover, 42nd ACM Symposium on Theory of Computing, pp.457-464, 2010.
, Approximation Algorithms, 2001.