Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an n x n matrix M and will receive n column-vectors of size n, denoted by v(1), ... , v(n), one by one. After seeing each vector...
详细信息
ISBN:
(纸本)9781450335362
Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an n x n matrix M and will receive n column-vectors of size n, denoted by v(1), ... , v(n), one by one. After seeing each vector we have to output the product Mv(i) before we can see the next vector. A naive algorithm can solve this problem using O(n(3)) time in total, and its running time can be slightly improved to O(n(3)/log(2) n) [Williams SODA'07]. We show that a conjecture that there is no truly subcubic (P(n(3-epsilon))) time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, d-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term "combinatorial algorithms" is interpreted as "Strassen-like algorithms" [Ballard et al. SPAA'11]. The conjecture also leads to hardness results for problems that were previously based on diverse problems and conjectures - such as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and multiphase thus providing a uniform way to prove polynomial hardness results for dynamicalgorithms;some of the new proofs are also simpler or even become trivial. The conjecture also leads to stronger and new, non-trivial, hardness results, e.g., for the fully-dynamic densest subgraph and diameter problems.
Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with o(mn) total update time, wheremis the number of edges...
详细信息
ISBN:
(纸本)9783662476727;9783662476710
Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with o(mn) total update time, wheremis the number of edges and n is the number of nodes in the graph [Henzinger et al. STOC 2014]. The algorithm is a combination of several different algorithms, each for a different m vs. n trade-off. For the case of m = Theta(n(1.5)) the running time is O(n(2.47)), just barely below mn = Theta(n(2.5)). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of (O) over tilde (min(m(7/6)n(2/3), m(3/4)n(5/4+o(1)), m(2/3)n(4/3+o(1))+ m(3/7)n(12/7+o)(1))). This gives, e.g., O(n(2.36)) for the notorious case m = Theta(n(1.5)). We obtain the same upper bounds for the problem of maintaining the strongly connected components of a directed graph undergoing edge deletions. Our algorithms are correct with high probabililty against an oblivious adversary.
The decremental single-source shortest paths (SSSP) problem concerns maintaining the distances between a given source node s to every node in an n-node m-edge graph G undergoing edge deletions. While its static counte...
详细信息
ISBN:
(纸本)9781479965175
The decremental single-source shortest paths (SSSP) problem concerns maintaining the distances between a given source node s to every node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be easily solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach (JACM 1981) has been the fastest known algorithm for three decades. With the loss of a (1 + epsilon)-approximation factor, the running time was recently improved to O(n(2+o(1))) by Bernstein and Roditty (SODA 2011), and more recently to O(n(1.8+o(1)) + m(1+o(1))) by Henzinger, Krinninger, and Nanongkai (SODA 2014). In this paper, we finally bring the running time of this case down to near-linear: We give a (1+ epsilon)-approximation algorithm with O(m(1+o(1))) total update time, thus obtaining near-linear time. Moreover, we obtain O(m(1+o(1)) log W) time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn log W) time is the O(mn(0.986) log W)-time algorithm by Henzinger, Krinninger, and Nanongkai (STOC 2014) which works for the general weighted directed case. In contrast to the previous results which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (d, epsilon)-hop set introduced by Cohen (JACM 2000) in the PRAM literature. A (d, c)-hop set of a graph G = (V, E) is a set E' of weighted edges such that the distance between any pair of nodes in G can be (1+ epsilon)-approximated by their d-hop distance (given by a path containing at most d edges) on G' = (V, E boolean OR E'). Our algorithm can maintain an (n(o(1)), epsilon)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain the distances on this hop set, we develop a monotone bounded-hop Even-Shiloach t
We consider dynamicalgorithms for maintaining Single-Source Reachability (SSR) and approximate Single-Source Shortest Paths (SSSP) on n-node m-edge directed graphs under edge deletions (decremental algorithms). The p...
详细信息
ISBN:
(纸本)9781450327107
We consider dynamicalgorithms for maintaining Single-Source Reachability (SSR) and approximate Single-Source Shortest Paths (SSSP) on n-node m-edge directed graphs under edge deletions (decremental algorithms). The previous fastest algorithm for SSR and SSSP goes back three decades to Even and Shiloach (JACM 1981);it has O(1) query time and O(mn) total update time (i.e., linear amortized update time if all edges are deleted). This algorithm serves as a building block for several other dynamicalgorithms. The question whether its total update time can be improved is a major, long standing, open problem. In this paper, we answer this question affirmatively. We obtain a randomized algorithm which, in a simplified form, achieves an O(mn(0.984)) expected total update time for SSR and (1 + epsilon)-approximate SSSP, where O(.) hides poly log n. We also extend our algorithm to achieve roughly the same running time for Strongly Connected Components (SCC), improving the algorithm of Roditty and Zwick (FOCS 2002), and an algorithm that improves the O(mn log W)-time al gorithm of Bernstein (STOC 2013) for approximating SSSP on weighted directed graphs, where the edge weights are integers from 1 to W. All our algorithms have constant query time in the worst case.
In this paper, we introduce a computational framework for studying dynamical systems. This framework can be used to prove the existence of certain behaviour in a given dynamical system at any finite (limited) resoluti...
详细信息
ISBN:
(纸本)9781479930357
In this paper, we introduce a computational framework for studying dynamical systems. This framework can be used to prove the existence of certain behaviour in a given dynamical system at any finite (limited) resolution automatically. The proposed framework is based on approximating the phase space topology of a given dynamical system at a finite resolution by adaptively partitioning it at rational points. Dyadic rationals and partition elements with disjoint interiors are employed to build a transparent partition that enables constructing an ideal combinatorial representation of a given dynamical system. Moreover, we introduce a new algorithmic strategy that overcomes the dependence on initial conditions, supports deriving ubiquitous conclusions, enables finding bifurcation points up to certain precision, and (most importantly) is computationally efficient. A set of simple yet powerful dynamic graph algorithms that were developed to support the new strategy are described in details. As an application, invariant sets and bifurcation points of the logistic map were computed.
The computation of the winning set for Buchi objectives in alternating games on graphs is a central problem in computer-aided verification with a large number of applications. The long-standing best known upper bound ...
详细信息
The computation of the winning set for Buchi objectives in alternating games on graphs is a central problem in computer-aided verification with a large number of applications. The long-standing best known upper bound for solving the problem is (O) over tilde (n. m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the 0(n m) boundary by presenting a new technique that reduces the running time to 0(n(2)). This bound also leads to O(n(2))-time algorithms for computing the set of almost-sure winning vertices for Buchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of 0(n,. m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n(3))), and (3) in Markov decision processes (improving for m > n(4/3) an earlier bound of O(m.,root m)). We then show how to maintain the winning set for Buchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in 0(n) amortized time per operation. Our algorithms are the first dynamicalgorithms for this problem. We then consider another core graph theoretic problem in verification of probabilistic systems, namely computing the maximal end-component decomposition of a graph. We present two improved static algorithms for the maximal end-component decomposition problem. Our first algorithm is an O(*** m)-time algorithm, and our second algorithm is an 0(n2)-time algorithm which is obtained using the same technique as for alternating Buchi games. Thus, we obtain an O(min{m . root m, n(2)})-time algorithm improving the long-standing O(n . m) time bound. Finally, we show how to maintain the maximal end-component decomposition of a graph under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per edge deletion, and O(m) worst-case time per edge insertion. Again, our algorithms are the first dynamicalgorithms for this problem.
We study dynamic (1 + epsilon)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomiz...
详细信息
ISBN:
(纸本)9780769551357
We study dynamic (1 + epsilon)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of (O) over tilde (mn) and constant query time by Roditty and Zwick [34] (FOCS 2004). The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach [23];it has a total update time of O(mn(2)) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of (o) over tilde (n(5/2)) and constant query time that has an additive error of two in addition to the 1 broken vertical bar epsilon multiplicative error. This beats the previous (o) over tilde (mn) time when m = Omega(n(3/2)). Note that the additive error is unavoidable since, even in the static case, an O(n(3-delta))-time (a so-called truly subcubic) combinatorial algorithm with 1+epsilon multiplicative error cannot have an additive error less than 2-epsilon, unless we make a major breakthrough for Boolean matrix multiplication [19] and many other long-standing problems [40]. The algorithm can also be turned into a (2 + epsilon)approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3 + epsilon)approximation algorithm with (O) over tilde (n(5/2+O(1/root log n))) running time of Bernstein and Roditty [12] (SODA 2011) in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of (O) over tilde (mn) and a query time of O(log log n). The algorithm has a multiplicative error of 1 + epsilon and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein in his STOC 2013 paper [11]. In order to achieve our results, we introduce two new techniques: (1) A monotone Even-Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree
We present faster and dynamicalgorithms for the following problems arising in probabilistic verification: Computation of the maximal end-component (mec) decomposition of Markov decision processes (MDPs), and of the a...
详细信息
ISBN:
(纸本)9780898719932
We present faster and dynamicalgorithms for the following problems arising in probabilistic verification: Computation of the maximal end-component (mec) decomposition of Markov decision processes (MDPs), and of the almost sure winning set for reachability and parity objectives in MDPs. We achieve the following running time for static algorithms in MDPs with graphs of n vertices and m edges: (1) O(m · min{m~(1/2), n~(2/3)}) for the mec decomposition, improving the longstanding O(m·n) bound; (2) O(m·n~(2/3)) for reachability objectives, improving the previous O(m · m~(1/2)) bound for m > n~(4/3); and (3) O(m · min{ m~(1/2), n~(2/3) } · log(d)) for parity objectives with d priorities, improving the previous O(m · m~(1/2) · d) bound. We also give incremental and decremental algorithms in linear time for mec decomposition and reachability objectives and O(m· log d) time for parity objectives.
Computing the winning set for Buchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solvi...
详细信息
ISBN:
(纸本)9781611972108
Computing the winning set for Buchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is O{top}~(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the O{top}~(n·m) boundary by presenting a new technique that reduces the running time to O(n~2). This bound also leads to O(n~2) time algorithms for computing the set of almost-sure winning vertices for Buchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of {top}O(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n~3)), and (3) in Markov decision processes (improving for m ＞ n~(4/3) an earlier bound of O(min(m~(1.5),m· n~(2/3))). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n~2), which is an improvement over earlier bounds for m ＞ n~(4/3). Finally, we show how to maintain the winning set for Buchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.
dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an undirected graph, subject to edge ins...
详细信息
dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an undirected graph, subject to edge insertions and deletions. In this paper, we study two more challenging, yet equally fundamental, problems. Subgraph connectivity asks us to maintain an understanding of connectivity under vertex updates: updates can turn vertices on and off, and queries refer to the subgraph induced by on vertices. (For instance, this is closer to applications in networks of routers, where node faults may occur.) We describe a data structure supporting vertex updates in (O) over tilde (m(2/3)) amortized time, where m denotes the number of edges in the graph. This greatly improves upon the previous result [T. M. Chan, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 2002, pp. 7-13], which required fast matrix multiplication and had an update time of O(m(0.94)). The new data structure is also simpler. Geometric connectivity asks us to maintain a dynamic set of n geometric objects and query connectivity in their intersection graph. (For instance, the intersection graph of balls describes connectivity in a network of sensors with bounded transmission radius.) Previously, nontrivial fully dynamic results were known only for special cases like axis-parallel line segments and rectangles. We provide similarly improved update times, (O) over tilde (n(2/3)), for these special cases. Moreover, we show how to obtain sublinear update bounds for virtually all families of geometric objects which allow sublinear time range queries. In particular, we obtain the first sublinear update time for arbitrary two-dimensional line segments: O*(n(9/10));for d-dimensional simplices: O*(n(1-1/d(2d+1)));and for d-dimensional balls: O*(n(1-1/(d+1)(2d+3))).
暂无评论