ﻻ يوجد ملخص باللغة العربية
We present a new dynamic matching sparsification scheme. From this scheme we derive a framework for dynamically rounding fractional matchings against emph{adaptive adversaries}. Plugging in known dynamic fractional matching algorithms into our framework, we obtain numerous randomized dynamic matching algorithms which work against adaptive adversaries (the first such algorithms, as all previous randomized algorithms for this problem assumed an emph{oblivious} adversary). In particular, for any constant $epsilon>0$, our framework yields $(2+epsilon)$-approximate algorithms with constant update time or polylog worst-case update time, as well as $(2-delta)$-approximate algorithms in bipartite graphs with arbitrarily-small polynomial update time, with all these algorithms guarantees holding against adaptive adversaries. All these results achieve emph{polynomially} better update time to approximation tradeoffs than previously known to be achievable against adaptive adversaries.
Designing dynamic graph algorithms against an adaptive adversary is a major goal in the field of dynamic graph algorithms. While a few such algorithms are known for spanning trees, matchings, and single-source shortest paths, very little was known fo
We present a framework for deterministically rounding a dynamic fractional matching. Applying our framework in a black-box manner on top of existing fractional matching algorithms, we derive the following new results: (1) The first deterministic algo
Given a dynamic digraph $G = (V,E)$ undergoing edge deletions and given $sin V$ and $epsilon>0$, we consider the problem of maintaining $(1+epsilon)$-approximate shortest path distances from $s$ to all vertices in $G$ over the sequence of deletions.
Given a directed graph $G = (V,E)$, undergoing an online sequence of edge deletions with $m$ edges in the initial version of $G$ and $n = |V|$, we consider the problem of maintaining all-pairs shortest paths (APSP) in $G$. Whilst this problem has b
In this paper, we study the average case complexity of the Unique Games problem. We propose a natural semi-random model, in which a unique game instance is generated in several steps. First an adversary selects a completely satisfiable instance of Un