In the decremental Single-Source Shortest Path problem (SSSP), we are given a weighted directed graph G = (V, E, w) undergoing edge deletions and a source vertex r is an element of V;let n = vertical bar V vertical ba...
详细信息
ISBN:
(纸本)9781728196213
In the decremental Single-Source Shortest Path problem (SSSP), we are given a weighted directed graph G = (V, E, w) undergoing edge deletions and a source vertex r is an element of V;let n = vertical bar V vertical bar, m = vertical bar E vertical bar and W be the aspect ratio of the graph. The goal is to obtain a data structure that maintains shortest paths from r to all vertices in V and can answer distance queries in O(1) time, as well as return the corresponding path P in O(vertical bar P vertical bar) time. This problem was first considered by Even and Shiloach [JACM'81], who provided an algorithm with total update time O(mn) for unweighted undirected graphs;this was later extended to directed weighted graphs [FOCS'95, STOC'99]. There are conditional lower bounds showing that O(mn) is in fact near-optimal [ESA'04, FOCS'14, STOC'15, STOC'20]. In a breakthrough result, Forster et al. showed that total update time min{m(7/6) n(2/3+o(1)), m(3/4) n(5/4+o(1))}polylog(W) = mn(0.9+o(1))polylog(W) is possible if the algorithm is allowed to return (1 + epsilon)-approximate paths, instead of exact ones [STOC'14, ICALP'15]. No further progress was made until Probst Gutenberg and Wulff-Nilsen [SODA'20] provided a new approach for the problem, which yields total time (O) over tilde (min{m(2/3) n(4/3) log W, (mn)(7/8) log W}) = (O) over tilde (min{n(8/3) log W, mn(3/4) log W}). Our result builds on this recent approach, but overcomes its limitations by introducing a significantly more powerful abstraction, as well as a different core subroutine. Our new framework yields a decremental (1 + epsilon)-approximate SSSP data structure with total update time (O) over tilde (n(2) log(4) W/epsilon). Our algorithm is thus near-optimal for dense graphs with polynomial edge-weights. Our framework can also be applied to sparse graphs to obtain total update time (O) over tilde (mn(2/3) log(3) W/epsilon). Combined, these data structures dominate all previous results. Like all previous o(mn)
Let G = (V, E, w) be a weighted, directed graph subject to a sequence of adversarial edge deletions. In the decremental single-source reachability problem (SSR), we are given a fixed source s and the goal is to mainta...
详细信息
ISBN:
(纸本)9781728196213
Let G = (V, E, w) be a weighted, directed graph subject to a sequence of adversarial edge deletions. In the decremental single-source reachability problem (SSR), we are given a fixed source s and the goal is to maintain a data structure that can answer path-queries s (sic) v for any v is an element of V. In the more general single-source shortest paths (SSSP) problem the goal is to return an approximate shortest path to v, and in the SCC problem the goal is to maintain strongly connected components of G and to answer path queries within each component. All of these problems have been very actively studied over the past two decades, but all the fast algorithms are randomized and, more significantly, they can only answer path queries if they assume a weaker model: they assume an oblivious adversary which is not adaptive and must fix the update sequence in advance. This assumption significantly limits the use of these data structures, most notably preventing them from being used as subroutines in static algorithms. All the above problems are notoriously difficult in the adaptive setting. In fact, the state-of-the-art is still the Even and Shiloach tree, which dates back all the way to 1981 [1] and achieves total update time O(mn). We present the first algorithms to break through this barrier. deterministic decremental SSR/SCC with total update time mn(2/3+o(1)) deterministic decremental SSSP with total update time n(2+2/3+o(1)) To achieve these results, we develop two general techniques for working with dynamic graphs. The first generalizes expander-based tools to dynamic directed graphs. While these tools have already proven very successful in undirected graphs, the underlying expander decomposition they rely on does not exist in directed graphs. We thus need to develop an efficient framework for using expanders in directed graphs, as well as overcome several technical challenges in processing directed expanders. We establish several powerful primitives that we hope w
dynamically reconfigurable systems are able to respond to changes in their oper- ational environments by reconfiguring themselves automatically. dynamic soft- ware product lines are dynamically reconfigurable systems ...
详细信息
dynamically reconfigurable systems are able to respond to changes in their oper- ational environments by reconfiguring themselves automatically. dynamic soft- ware product lines are dynamically reconfigurable systems with an explicit vari- ability model that guides the reconfiguration. In this work, feature models are used as the variability model. Features are assumed to be mapped to system's components that realize them. A feature model corresponds to a constraint sat- isfaction problem (CSP), and determines the valid configurations of the system. An emerging situation in the environment can lead to some relevant changes to the current configuration: some features must be activated, and some must be deactivated. Due to constraint propagation, the status of other features might need to be changed as well. However, considering the feature state migration costs, one would like to avoid such changes to the greatest extent possible in order to mitigate the cost of the disruption to the system's operation. In this work, we devised a dynamic constraint satisfaction algorithm that efficiently considers feature state changes to be applied to the current configuration while confronting changes in the environment so that the new configuration will be valid and the requirements of the new situation will be satisfied with the mini- mum cost. A set of heuristics regarding feature model relations and the overall structure of feature models are also proposed to enhance the efficiency of the algorithm.
We give new upper and lower bounds for the dynamic set cover problem. First, we give a (1 + epsilon)f-approximation for fully dynamic set cover in O(f(2) log n/epsilon(5)) (amortized) update time, for any epsilon >...
详细信息
ISBN:
(纸本)9781450367059
We give new upper and lower bounds for the dynamic set cover problem. First, we give a (1 + epsilon)f-approximation for fully dynamic set cover in O(f(2) log n/epsilon(5)) (amortized) update time, for any epsilon > 0, where f is the maximum number of sets that an element belongs to. In the decremental setting, the update time can be improved to O(f(2)/epsilon(5)), while still obtaining an (1 + epsilon)f-approximation. These are the first algorithms that obtain an approximation factor linear in f for dynamic set cover, thereby almost matching the best bounds known in the offline setting and improving upon the previous best approximation of O(f(2)) in the dynamic setting. To complement our upper bounds, we also show that a linear dependence of the update time on f is necessary unless we can tolerate much worse approximation factors. Using the recent distributed PCP-framework, we show that any dynamic set cover algorithm that has an amortized update time of O(f(1-epsilon)) must have an approximation factor that is Omega(n(delta)) for some constant delta > 0 under the Strong Exponential Time Hypothesis.
Software-defined networking (SDN) and network function virtualization (NFV) together form a promising paradigm that enables the slicing of heterogeneous network resources for agile and efficient service customization....
详细信息
ISBN:
(纸本)9781728109626
Software-defined networking (SDN) and network function virtualization (NFV) together form a promising paradigm that enables the slicing of heterogeneous network resources for agile and efficient service customization. Among other techniques, virtual network function (VNF) mapping and scheduling are crucial to the deployment of SDN/NFV-enabled network services. In this paper, to enhance the performance of service provisioning, dynamic VNF mapping and scheduling are jointly investigated. Specifically, to achieve load balancing with QoS guarantee, we first formulate the VNF mapping and scheduling problem as a mixed integer linear programming (MILP). We then propose a two-stage online algorithm to address the NP-hardness of the MILP. In particular, when new service arrives, we map and schedule the VNFs on a service function chain (SFC) by greedily minimizing the waiting time of VNFs. If the delay requirement cannot be satisfied after the first stage, a delay-aware rescheduling scheme is triggered, in which selected existing VNFs are remapped and rescheduled. The proposed dynamic approach achieves flexible function placement and increases service acceptance ratio. Simulation results are provided to validate the effectiveness of the proposed algorithm.
Most of the existing techniques for palmprint recognition rely on metrics, typically based on static functions, which evaluate the distance between a pair of features. In this paper, we propose a new technique for pal...
详细信息
Most of the existing techniques for palmprint recognition rely on metrics, typically based on static functions, which evaluate the distance between a pair of features. In this paper, we propose a new technique for palmprint verification based on a dynamical system approach for principal palm lines matching. The proposed dynamic algorithm is recursive and involves a positive linear dynamical system, whose evolution depends on the matching level between the two input images. In a preprocessing phase, the procedure iteratively erodes both of the images to be compared, by eliminating points in each image that do not have enough close neighboring points both in the image itself and the comparison image. As a result of the iterations, only the points that have enough neighboring points in both the image itself and in the comparison image can survive. Thus, the output of the dynamical system converges either to zero, when a deep mismatch exists between the two images, or to a high value, when a good matching is observed. The results, in terms of verification, are in line with the state-of-the-art results in the current literature. The main advantage of the approach is its robustness when dealing with low-resolution and noisy images. The impact of noise (e.g., salt and pepper noise) is effectively reduced: images corrupted with such noise are easily recognized, while a randomly generated image is rejected even when compared with itself.
It is of crucial importance to develop an efficient numerical method to investigate the mechanism of grout diffusion and migration in fractured rock masses. However, most existing models only concentrate on the grout ...
详细信息
It is of crucial importance to develop an efficient numerical method to investigate the mechanism of grout diffusion and migration in fractured rock masses. However, most existing models only concentrate on the grout flow in a single fracture and most existing algorithms for large-scale fracture networks have high computational cost. A new dynamic diffusion and migration algorithm for grout was proposed and applied to the two-dimensional fracture network in this paper. Based on the geometric relationship between the fracture network nodes, an effective and feasible generation method of the connectivity matrix was proposed to realize the digitization of the topological structure of the fracture network. Finally, the Fracture Networks Grouting Diffusion Program (FNGDP) was developed to visualize the entire process of grout diffusion and migration in fracture networks. Compared with other algorithms, the proposed algorithm can realistically simulate the grouting process and greatly reduce computing time.
Gröbner bases are a necessary tool to solve many problems involving polynomial ideals, including applications such as nonlinear polynomial system solving, integer programming and cryptography. Traditional Grö...
详细信息
Gröbner bases are a necessary tool to solve many problems involving polynomial ideals, including applications such as nonlinear polynomial system solving, integer programming and cryptography. Traditional Gröbner Basis algorithms are static, in the sense that they receive a monomial order as input and it is fixed during the entire execution of the algorithm. dynamic algorithms, in contrast, allow this monomial ordering to change to generate smaller output bases and, hopefully, fewer polynomial reductions. All but one of the previously proposed dynamic algorithms are restricted, meaning that once they choose a leading monomial for a certain polynomial, that choice cannot be unmade. In this work, we focus on exploring unrestricted dynamic algorithms, studying the relation of monomial orderings to Newton polyhedra and proposing four new unrestricted algorithms that avoid evaluating too many monomial orderings by using a neighborhood construction for monomial orders. We also propose a new heuristic, called the Mixed heuristic, for monomial order evaluation in dynamic algorithms. Our experiments show that although the restricted algorithms perform better with respect to running time, our unrestricted algorithms find orders that lead to smaller Gröbner Bases for many instances and significantly lower degree polynomials in average. Additionally, we provide a comparison between the previously defined Hilbert and Betti heuristics and our Mixed heuristic, showing it performs better than the Betti heuristic in most aspects and is competitive with the Hilbert heuristic overall. ...
Mixed precision is a promising approach to save energy in iterative refinement algorithms since it obtains speed-up without necessitating additional cores and parallelization. However, conventional mixed precision met...
详细信息
Mixed precision is a promising approach to save energy in iterative refinement algorithms since it obtains speed-up without necessitating additional cores and parallelization. However, conventional mixed precision methods utilize statically defined precision in a loop, thus hindering further speed-up and energy savings. We overcome this problem by proposing novel methods which allow iterative refinement to utilize variable precision arithmetic dynamically in a loop (i.e., a trans-precision approach). Our methods restructure a numeric algorithmdynamically according to runtime numeric behavior and remove unnecessary accuracy checks. We implemented our methods by extending one conventional mixed precision iterative refinement algorithm on an Intel Xeon E5-2650 2GHz core with MKL 2017 and XBLAS 1.0. Our dynamic precision approach demonstrates 2.0-2.6x speed-up and 1.8-2.4x energy savings compared with mixed precision iterative refinement when double precision solution accuracy is required for forward error and with matrix dimensions ranging from 4K to 32K.
Computing the Strongly-Connected Components (SCCs) in a graph G = (V, E) is known to take only O(m + n) time using an algorithm by Tarjan from 1972[SICOMP 72] where m = vertical bar E vertical bar, n = vertical bar V ...
详细信息
ISBN:
(纸本)9781450367059
Computing the Strongly-Connected Components (SCCs) in a graph G = (V, E) is known to take only O(m + n) time using an algorithm by Tarjan from 1972[SICOMP 72] where m = vertical bar E vertical bar, n = vertical bar V vertical bar. For fully-dynamic graphs, conditional lower bounds provide evidence that the update time cannot be improved by polynomial factors over recomputing the SCCs from scratch after every update. Nevertheless, substantial progress has been made to find algorithms with fast update time for decremental graphs, i.e. graphs that undergo edge deletions. In this paper, we present the first algorithm for general decremental graphs that maintains the SCCs in total update time (O) over tilde (m)(1), thus only a polylogarithmic factor from the optimal running time. Previously such a result was only known for the special case of planar graphs [Italiano et al, STOC 17]. Our result should be compared to the formerly best algorithm for general graphs achieving (O) over tilde (m root n) total update time by Chechik ***. [FOCS 16] which improved upon a breakthrough result leading to O(mn(0.9+o(1))) total update time by Henzinger, Krinninger and Nanongkai [STOC 14, ICALP 15];these results in turn improved upon the longstanding bound of O(mn) by Roditty and Zwick [STOC 04]. All of the above results also apply to the decremental Single-Source Reachability (SSR) problem, which can be reduced to decrementally maintaining SCCs. A bound of O(mn) total update time for decremental SSR was established already in 1981 by Even and Shiloach [JACM 81].
暂无评论