1,721,029 research outputs found
Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees
No full textLet G be an n-node and m-edge positively real-weighted undirected graph. For any given integer f≥ 1 , we study the problem of designing a sparse f-edge-fault-tolerant (f-EFT) σ-approximate single-source shortest-path tree (σ-ASPT), namely a subgraph of G having as few edges as possible and which, following the failure of a set F of at most f edges in G, contains paths from a fixed source that are stretched by a factor of at most σ. To this respect, we provide an algorithm that efficiently computes an f-EFT (2 | F| + 1) -ASPT of size O(fn). Our structure improves on a previous related construction designed for unweighted graphs, having the same size but guaranteeing a larger stretch factor of 3 (f+ 1) , plus an additive term of (f+ 1) log n. Then, we show how to convert our structure into an efficient f-EFT single-source distance oracle, that can be built in O(fmα(m,n)+fnlog3n) time, has size O(fnlog 2n) , and in O(| F| 2log 2n) time is able to report a (2 | F| + 1) -approximate distance from the source to any node in G- F. Moreover, our oracle can return a corresponding approximate path in the same amount of time plus the path’s size. The oracle is obtained by tackling another fundamental problem, namely that of updating a minimum spanning forest (MSF) of G following a batch of k simultaneous modification (i.e., edge insertions, deletions and weight changes). For this problem, we build in O(mlog 3n) time an oracle of size O(mlog 2n) , that reports in O(k2log 2n) time the (at most 2k) edges either exiting from or entering into the MSF. Finally, for any integer k≥ 1 , we complement all our results with a lower bound of Ω(n1+1k) to the size of any f-EFT σ-ASPT with f≥ log n and σ<3k+1k+1, that holds if the Erdős’ girth conjecture is true
Cutting bamboo down to size
No full textThis paper studies the problem of programming a robotic panda gardener to keep a bamboo garden from obstructing the view of the lake by your house. The garden consists of n bamboo stalks with known daily growth rates and the gardener can cut at most one bamboo per day. As a computer scientist, you found out that this problem has already been formalized in [Gasieniec et al., SOFSEM'17] as the Bamboo Garden Trimming (BGT) problem, where the goal is that of computing a perpetual schedule (i.e., the sequence of bamboos to cut) for the robotic gardener to follow in order to minimize the makespan, i.e., the maximum height ever reached by a bamboo. Two natural strategies are Reduce-Max and Reduce-Fastest(x). Reduce-Max trims the tallest bamboo of the day, while Reduce-Fastest(x) trims the fastest growing bamboo among the ones that are taller than x. It is known that Reduce-Max and Reduce-Fastest(x) achieve a makespan of O(log n) and 4 for the best choice of x = 2, respectively. We prove the first constant upper bound of 9 for Reduce-Max and improve the one for Reduce-Fastest(x) to 3+2v5 < 2.62 for x = 1 + v15. Another critical aspect stems from the fact that your robotic gardener has a limited amount of processing power and memory. It is then important for the algorithm to be able to quickly determine the next bamboo to cut while requiring at most linear space. We formalize this aspect as the problem of designing a Trimming Oracle data structure, and we provide three efficient Trimming Oracles implementing different perpetual schedules, including those produced by Reduce-Max and Reduce-Fastest(x)
Tolerance is Necessary for Stability: Single-Peaked Swap Schelling Games
No full textResidential segregation in metropolitan areas is a phenomenon that can be observed all over the world. Recently, this was investigated via game-theoretic models. There, selfish agents of two types are equipped with a monotone utility function that ensures higher utility if an agent has more same-type neighbors. The agents strategically choose their location on a given graph that serves as residential area to maximize their utility. However, sociological polls suggest that real-world agents are actually favoring mixed-type neighborhoods, and hence should be modeled via non-monotone utility functions. To address this, we study Swap Schelling Games with single-peaked utility functions. Our main finding is that tolerance, i.e., agents favoring fifty-fifty neighborhoods or being in the minority, is necessary for equilibrium existence on almost regular or bipartite graphs. Regarding the quality of equilibria, we derive (almost) tight bounds on the Price of Anarchy and the Price of Stability. In particular, we show that the latter is constant on bipartite and almost regular graphs
Near-optimal deterministic single-source distance sensitivity oracles
No full textGiven a graph with a distinguished source vertex s, the Single Source Replacement Paths (SSRP) problem is to compute and output, for any target vertex t and edge e, the length d(s, t, e) of a shortest path from s to t that avoids a failing edge e. A Single-Source Distance Sensitivity Oracle (Single-Source DSO) is a compact data structure that answers queries of the form (t, e) by returning the distance d(s, t, e). We show how to deterministically compress the output of the SSRP problem on n-vertex, m-edge graphs with integer edge weights in the range [1, M] into a Single-Source DSO that has size O(M1/2n3/2) and query time Oe(1). We prove that the space requirement is optimal (up to the word size). Our techniques can also handle vertex failures within the same bounds. Chechik and Cohen [SODA 2019] presented a combinatorial, randomized Oe(m√n + n2) time SSRP algorithm for undirected and unweighted graphs. We derandomize their algorithm with the same asymptotic running time and apply our compression to obtain a deterministic Single-Source DSO with Oe(m√n +n2) preprocessing time, O(n3/2) space, and Oe(1) query time. Our combinatorial Single-Source DSO has near-optimal space, preprocessing and query time for unweighted graphs, improving the preprocessing time by a √n -factor compared to previous results with o(n2) space. Grandoni and Vassilevska Williams [FOCS 2012, TALG 2020] gave an algebraic, randomized Oe(Mnω) time SSRP algorithm for (undirected and directed) graphs with integer edge weights in the range [1, M], where ω < 2.373 is the matrix multiplication exponent. We derandomize it for undirected graphs and apply our compression to obtain an algebraic Single-Source DSO with Oe(Mnω) preprocessing time, O(M1/2 n3/2) space, and Oe(1) query time. This improves the preprocessing time of algebraic Single-Source DSOs by polynomial factors compared to previous o(n2)-space oracles. We also present further improvements of our Single-Source DSOs. We show that the query time can be reduced to a constant at the cost of increasing the size of the oracle to O(M1/3 n5/3) and that all our oracles can be made path-reporting. On sparse graphs with m = O(nM5/74/−4ε) edges, for any constant ε > 0, we reduce the preprocessing to randomized Oe(M7/8 m1/2 n11/8) = O(n2−ε/2) time. To the best of our knowledge, this is the first truly subquadratic time algorithm for building Single-Source DSOs on sparse graphs
Bounded-Distance Network Creation Games
No full textA network creation game simulates a decentralized and noncooperative construction of a communication network. Informally, there are n players sitting on the network nodes, which attempt to establish a reciprocal communication by activating, thereby incurring a certain cost, any of their incident links. The goal of each player is to have all the other nodes as close as possible in the resulting network, while buying as few links as possible. According to this intuition, any model of the game must then appropriately address a balance between these two conflicting objectives. Motivated by the fact that a player might have a strong requirement about her centrality in the network, we introduce a new setting in which a player who maintains her (maximum or average) distance to the other nodes within a given bound incurs a cost equal to the number of activated edges; otherwise her cost is unbounded. We study the problem of understanding the structure of pure Nash equilibria of the resulting games, which we call MaxBD and SumBD, respectively. For both games, we show that when distance bounds associated with players are nonuniform, then equilibria can be arbitrarily bad. On the other hand, for MaxBD, we show that when nodes have a uniform bound D ≥ 3 on the maximum distance, then the price of anarchy (PoA) is lower and upper bounded by 2 and O(n1/⌊log3 D ⌋+1), respectively (i.e., PoA is constant as soon as D is Ω(nε), for any ε > 0), while for the interesting case D=2, we are able to prove that the PoA is Ω(&sqrt;n) and O(&sqrt;n log n). For the uniform SumBD, we obtain similar (asymptotically) results and moreover show that PoA becomes constant as soon as the bound on the average distance is 2ω(&sqrt;log n)
Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game
Full text linkConsider a communication network represented by a directed graph G=(V,E) of n nodes and m edges. Assume that edges in E are partitioned into two sets: a set C of edges with a fixed non-negative real cost, and a set P of edges whose costs are instead priced by a leader. This is done with the final intent of maximizing a revenue that will be returned for their use by a follower, whose goal in turn is to select for his communication purposes a subnetwork of Gminimizing a given objective function of the edge costs. In this paper, we study the natural setting in which the follower computes a single-source shortest paths tree of G, and then returns to the leader a payment equal to the sum of the selected priceable edges. Thus, the problem can be modeled as a one-round two-player Stackelberg Network Pricing Game, but with the novelty that the objective functions of the two players are asymmetric, in that the revenue returned to the leader for any of her selected edges is not equal to the cost of such an edge in the follower’s solution. As is shown, for any ϵ>0 and unless P=NP, the leader’s problem of finding an optimal pricing is not approximable within n1/2−ϵ, while, if G is unweighted and the leader can only decide which of her edges enter in the solution, then the problem is not approximable within n1/3−ϵ. On the positive side, we devise a strongly polynomial-time O(n)-approximation algorithm, which favorably compares against the classic approach based on a single-price algorithm. Finally, motivated by practical applications, we consider the special cases in which edges in C are unweighted and happen to form two popular network topologies, namely stars and chains, and we provide a comprehensive characterization of their computational tractability
Space-Efficient Fault-Tolerant Diameter Oracles
Full text linkWe design f-edge fault-tolerant diameter oracles (f-FDO, or simply FDO if f = 1). For a given directed or undirected and possibly edge-weighted graph G with n vertices and m edges and a positive integer f, we preprocess the graph and construct a data structure that, when queried with a set F of edges, where |F|f, returns the diameter of GF. An f-FDO has stretch σ1 if the returned value bD satisfies diam(GF)bDσ diam(GF). For the case of a single edge failure (f = 1) in an unweighted directed graph, there exists an approximate FDO by Henzinger et al. [ITCS 2017] with stretch (1 + ε), constant query time, space O(m), and a combinatorial preprocessing time of eO(mn + n1.5p Dm/ε ), where D is the diameter. We present an FDO for directed graphs with the same stretch, query time, and space. It has a preprocessing time of eO(mn + n2/ε), which is better for constant ε > 0. The preprocessing time nearly matches a conditional lower bound for combinatorial algorithms, also by Henzinger et al. With fast matrix multiplication, we achieve a preprocessing time of eO(n2.5794 + n2/ε). We further prove an information-theoretic lower bound showing that any FDO with stretch better than 3/2 requires Ω(m) bits of space. Thus, for constant 0 < ε < 3/2, our combinatorial (1 + ε)-approximate FDO is near-optimal in all parameters. In the case of multiple edge failures (f > 1) in undirected graphs with non-negative edge weights, we give an f-FDO with stretch (f + 2), query time O(f2 log2 n), eO(fn) space, and preprocessing time eO(fm). We complement this with a lower bound excluding any finite stretch in o(fn) space. Many real-world networks have polylogarithmic diameter. We show that for those graphs and up to f = o(log n/ log log n) failures one can swap approximation for query time and space. We present an exact combinatorial f-FDO with preprocessing time mn1+o(1), query time no(1), and space n2+o(1). When using fast matrix multiplication instead, the preprocessing time can be improved to nω+o(1), where ω < 2.373 is the matrix multiplication exponent
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
