اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدFully Dynamic Matching: Beating 2-Approximation in $Delta^epsilon$ Update Time
77
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In fully dynamic graphs, we know how to maintain a 2-approximation of maximum matching extremely fast, that is, in polylogarithmic update time or better. In a sharp contrast and despite extensive studies, all known algorithms that maintain a $2-Omega(1)$ approximate matching are much slower. Understanding this gap and, in particular, determining the best possible update time for algorithms providing a better-than-2 approximate matching is a major open question. In this paper, we show that for any constant $epsilon > 0$, there is a randomized algorithm that with high probability maintains a $2-Omega(1)$ approximate maximum matching of a fully-dynamic general graph in worst-case update time $O(Delta^{epsilon}+text{polylog } n)$, where $Delta$ is the maximum degree. Previously, the fastest fully dynamic matching algorithm providing a better-than-2 approximation had $O(m^{1/4})$ update-time [Bernstein and Stein, SODA 2016]. A faster algorithm with update-time $O(n^epsilon)$ was known, but worked only for maintaining the size (and not the edges) of the matching in bipartite graphs [Bhattacharya, Henzinger, and Nanongkai, STOC 2016].
قيم البحث
اقرأ أيضاً
The problem of (vertex) $(Delta+1)$-coloring a graph of maximum degree $Delta$ has been extremely well-studied over the years in various settings and models. Surprisingly, for the dynamic setting, almost nothing was known until recently. In SODA18, B
hattacharya, Chakrabarty, Henzinger and Nanongkai devised a randomized data structure for maintaining a $(Delta+1)$-coloring with $O(log Delta)$ expected amortized update time. In this paper, we present a $(Delta+1)$-coloring data structure that achieves a constant amortized update time and show that this time bound holds not only in expectation but also with high probability.
We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph---which undergoes both edge insertions and deletions---in polylogarithmic time. Our algorithm is randomized and, per update, takes $O(log^2 Delta
cdot log^2 n)$ expected time. Furthermore, the algorithm can be adjusted to have $O(log^2 Delta cdot log^4 n)$ worst-case update-time with high probability. Here, $n$ denotes the number of vertices and $Delta$ is the maximum degree in the graph. The MIS problem in fully dynamic graphs has attracted significant attention after a breakthrough result of Assadi, Onak, Schieber, and Solomon [STOC18] who presented an algorithm with $O(m^{3/4})$ update-time (and thus broke the natural $Omega(m)$ barrier) where $m$ denotes the number of edges in the graph. This result was improved in a series of subsequent papers, though, the update-time remained polynomial. In particular, the fastest algorithm prior to our work had $widetilde{O}(min{sqrt{n}, m^{1/3}})$ update-time [Assadi et al. SODA19]. Our algorithm maintains the lexicographically first MIS over a random order of the vertices. As a result, the same algorithm also maintains a 3-approximation of correlation clustering. We also show that a simpler variant of our algorithm can be used to maintain a random-order lexicographically first maximal matching in the same update-time.
Let $G=(V, E)$ be a given edge-weighted graph and let its {em realization} $mathcal{G}$ be a random subgraph of $G$ that includes each edge $e in E$ independently with probability $p$. In the {em stochastic matching} problem, the goal is to pick a sp
arse subgraph $Q$ of $G$ without knowing the realization $mathcal{G}$, such that the maximum weight matching among the realized edges of $Q$ (i.e. graph $Q cap mathcal{G}$) in expectation approximates the maximum weight matching of the whole realization $mathcal{G}$. In this paper, we prove that for any desirably small $epsilon in (0, 1)$, every graph $G$ has a subgraph $Q$ that guarantees a $(1-epsilon)$-approximation and has maximum degree only $O_{epsilon, p}(1)$. That is, the maximum degree of $Q$ depends only on $epsilon$ and $p$ (both of which are known to be necessary) and not for example on the number of nodes in $G$, the edge-weights, etc. The stochastic matching problem has been studied extensively on both weighted and unweighted graphs. Previously, only existence of (close to) half-approximate subgraphs was known for weighted graphs [Yamaguchi and Maehara, SODA18; Behnezhad et al., SODA19]. Our result substantially improves over these works, matches the state-of-the-art for unweighted graphs [Behnezhad et al., STOC20], and essentially settles the approximation factor.
The maximum matching problem in dynamic graphs subject to edge updates (insertions and deletions) has received much attention over the last few years; a multitude of approximation/time tradeoffs were obtained, improving upon the folklore algorithm, w
hich maintains a maximal (and hence $2$-approximate) matching in $O(n)$ worst-case update time in $n$-node graphs. We present the first deterministic algorithm which outperforms the folklore algorithm in terms of {em both} approximation ratio and worst-case update time. Specifically, we give a $(2-Omega(1))$-approximate algorithm with $O(sqrt{n}sqrt[8]{m})=O(n^{3/4})$ worst-case update time in $n$-node, $m$-edge graphs. For sufficiently small constant $epsilon>0$, no deterministic $(2+epsilon)$-approximate algorithm with worst-case update time $O(n^{0.99})$ was known. Our second result is the first deterministic $(2+epsilon)$-approximate (weighted) matching algorithm with $O_epsilon(1)cdot O(sqrt[4]{m}) = O_epsilon(1)cdot O(sqrt{n})$ worst-case update time.
In the dynamic minimum set cover problem, a challenge is to minimize the update time while guaranteeing close to the optimal $min(O(log n), f)$ approximation factor. (Throughout, $m$, $n$, $f$, and $C$ are parameters denoting the maximum number of se
ts, number of elements, frequency, and the cost range.) In the high-frequency range, when $f=Omega(log n)$, this was achieved by a deterministic $O(log n)$-approximation algorithm with $O(f log n)$ amortized update time [Gupta et al. STOC17]. In the low-frequency range, the line of work by Gupta et al. [STOC17], Abboud et al. [STOC19], and Bhattacharya et al. [ICALP15, IPCO17, FOCS19] led to a deterministic $(1+epsilon)f$-approximation algorithm with $O(f log (Cn)/epsilon^2)$ amortized update time. In this paper we improve the latter update time and provide the first bounds that subsume (and sometimes improve) the state-of-the-art dynamic vertex cover algorithms. We obtain: 1. $(1+epsilon)f$-approximation ratio in $O(flog^2 (Cn)/epsilon^3)$ worst-case update time: No non-trivial worst-case update time was previously known for dynamic set cover. Our bound subsumes and improves by a logarithmic factor the $O(log^3 n/text{poly}(epsilon))$ worst-case update time for unweighted dynamic vertex cover (i.e., when $f=2$ and $C=1$) by Bhattacharya et al. [SODA17]. 2. $(1+epsilon)f$-approximation ratio in $Oleft((f^2/epsilon^3)+(f/epsilon^2) log Cright)$ amortized update time: This result improves the previous $O(f log (Cn)/epsilon^2)$ update time bound for most values of $f$ in the low-frequency range, i.e. whenever $f=o(log n)$. It is the first that is independent of $m$ and $n$. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [SODA19] for unweighted dynamic vertex cover (i.e., when $f = 2$ and $C = 1$).
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
