1,721,004 research outputs found
Light Euclidean Spanners with Steiner Points
Full text linkThe FOCS'19 paper of Le and Solomon [Hung Le and Shay Solomon, 2019], culminating a long line of research on Euclidean spanners, proves that the lightness (normalized weight) of the greedy (1+ε)-spanner in ℝ^d is Õ(ε^{-d}) for any d = O(1) and any ε = Ω(n^{-1/(d-1)}) (where Õ hides polylogarithmic factors of 1/ε), and also shows the existence of point sets in ℝ^d for which any (1+ε)-spanner must have lightness Ω(ε^{-d}). Given this tight bound on the lightness, a natural arising question is whether a better lightness bound can be achieved using Steiner points.
Our first result is a construction of Steiner spanners in ℝ² with lightness O(ε^{-1} log Δ), where Δ is the spread of the point set. In the regime of Δ ≪ 2^(1/ε), this provides an improvement over the lightness bound of [Hung Le and Shay Solomon, 2019]; this regime of parameters is of practical interest, as point sets arising in real-life applications (e.g., for various random distributions) have polynomially bounded spread, while in spanner applications ε often controls the precision, and it sometimes needs to be much smaller than O(1/log n). Moreover, for spread polynomially bounded in 1/ε, this upper bound provides a quadratic improvement over the non-Steiner bound of [Hung Le and Shay Solomon, 2019], We then demonstrate that such a light spanner can be constructed in O_ε(n) time for polynomially bounded spread, where O_ε hides a factor of poly(1/(ε)). Finally, we extend the construction to higher dimensions, proving a lightness upper bound of Õ(ε^{-(d+1)/2} + ε^{-2} log Δ) for any 3 ≤ d = O(1) and any ε = Ω(n^{-1/(d-1)})
Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
Full text linkIn graph sparsification, the goal has almost always been of global nature: compress a graph into a smaller subgraph (sparsifier) that maintains certain features of the original graph.
Algorithms can then run on the sparsifier, which in many cases leads to improvements in the overall runtime and memory.
This paper studies sparsifiers that have bounded (maximum) degree, and are thus locally sparse, aiming to improve local measures of runtime and memory. To improve those local measures, it is important to be able to compute such sparsifiers locally.
We initiate the study of local algorithms for bounded degree sparsifiers in unweighted sparse graphs, focusing on the problems of vertex cover, matching, and independent set. Let \eps > 0 be a slack parameter and \alpha \ge 1 be a density parameter.
We devise local algorithms for computing:
1. A (1+\eps)-vertex cover sparsifier of degree O(\alpha / \eps), for any graph of arboricity \alpha.\footnote{In a graph of arboricity \alpha the average degree of any induced subgraph is at most 2\alpha.}
2. A (1+\eps)-maximum matching sparsifier and also a (1+\eps)-maximal matching sparsifier of degree O(\alpha / \eps, for any graph of arboricity \alpha.
3. A (1+\eps)-independent set sparsifier of degree O(\alpha^2 / \eps), for any graph of average degree \alpha.
Our algorithms require only a single communication round in the standard message passing model of distributed computing,
and moreover, they can be simulated locally in a trivial way.
As an immediate application we can extend results from distributed computing and local computation algorithms that apply to graphs of degree bounded by d to graphs of arboricity O(d / \eps) or average degree O(d^2 / \eps), at the expense of increasing the approximation guarantee by a factor of (1+\eps). In particular, we can extend the plethora of recent local computation algorithms for approximate maximum and maximal matching from bounded degree graphs to bounded arboricity graphs with a negligible loss in the approximation guarantee.
The inherently local behavior of our algorithms can be used to amplify the approximation guarantee of any sparsifier in time roughly linear in its size,
which has immediate applications in the area of dynamic graph algorithms. In particular, the state-of-the-art algorithm for
maintaining (2-\eps)-vertex cover (VC) is at least linear in the graph size, even in dynamic forests. We provide a reduction from the dynamic to the static case, showing that if a t-VC can be computed from scratch in time T(n) in any (sub)family of graphs with arboricity bounded by \alpha, for an arbitrary t \ge 1,
then a (t+\eps)-VC can be maintained with update time \frac{T(n)}{O((n / \alpha) \cdot \eps^2)}, for any \eps > 0. For planar graphs this yields an algorithm for maintaining a (1+\eps)-VC with constant update time for any constant \eps > 0
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
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Dispelling the Myths Behind First-author Citation Counts
Full text linkWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach
Full text linkIn the (fully) dynamic set cover problem, we have a collection of m sets from a universe of size n that undergo element insertions and deletions; the goal is to maintain an approximate set cover of the universe after each update. We give an O(f²) update time algorithm for this problem that achieves an f-approximation, where f is the maximum number of sets that an element belongs to; under the unique games conjecture, this approximation is best possible for any fixed f. This is the first algorithm for dynamic set cover with approximation ratio that exactly matches f (as opposed to almost f in prior work), as well as the first one with runtime independent of n,m (for any approximation factor of o(f³)).
Prior to our work, the state-of-the-art algorithms for this problem were O(f²) update time algorithms of Gupta et al. [STOC'17] and Bhattacharya et al. [IPCO'17] with O(f³) approximation, and the recent algorithm of Bhattacharya {et al. } [FOCS'19] with O(f⋅log{n}/ε²) update time and (1+ε)⋅f approximation, improving the O(f²⋅log{n}/ε⁵) bound of Abboud et al. [STOC'19].
The key technical ingredient of our work is an algorithm for maintaining a maximal matching in a dynamic hypergraph of rank r - where each hyperedge has at most r vertices - that undergoes hyperedge insertions and deletions in O(r²) amortized update time; our algorithm is randomized, and the bound on the update time holds in expectation and with high probability. This result generalizes the maximal matching algorithm of Solomon [FOCS'16] with constant update time in ordinary graphs to hypergraphs, and is of independent merit; the previous state-of-the-art algorithms for set cover do not translate to (integral) matchings for hypergraphs, let alone a maximal one. Our quantitative result for the set cover problem is translated directly from this qualitative result for maximal matching using standard reductions.
An important advantage of our approach over the previous ones for approximation (1+ε)⋅f (by Abboud et al. [STOC'19] and Bhattacharya et al. [FOCS'19]) is that it is inherently local and can thus be distributed efficiently to achieve low amortized round and message complexities
Improved Dynamic Graph Coloring
Full text linkThis paper studies the fundamental problem of graph coloring in fully dynamic graphs. Since the problem of computing an optimal coloring, or even approximating it to within n^{1-epsilon} for any epsilon > 0, is NP-hard in static graphs, there is no hope to achieve any meaningful computational results for general graphs in the dynamic setting. It is therefore only natural to consider the combinatorial aspects of dynamic coloring, or alternatively, study restricted families of graphs.
Towards understanding the combinatorial aspects of this problem, one may assume a black-box access to a static algorithm for C-coloring any subgraph of the dynamic graph, and investigate the trade-off between the number of colors and the number of recolorings per update step. Optimizing the number of recolorings, sometimes referred to as the recourse bound, is important for various practical applications. In WADS'17, Barba et al. devised two complementary algorithms: For any beta > 0, the first (respectively, second) maintains an O(C beta n^{1/beta}) (resp., O(C beta))-coloring while recoloring O(beta) (resp., O(beta n^{1/beta})) vertices per update. Barba et al. also showed that the second trade-off appears to exhibit the right behavior, at least for beta = O(1): Any algorithm that maintains a c-coloring of an n-vertex dynamic forest must recolor Omega(n^{2/(c(c-1))}) vertices per update, for any constant c >= 2. Our contribution is two-fold:
- We devise a new algorithm for general graphs that improves significantly upon the first trade-off in a wide range of parameters: For any beta > 0, we get a O~(C/(beta)log^2 n)-coloring with O(beta) recolorings per update, where the O~ notation supresses polyloglog(n) factors. In particular, for beta = O(1) we get constant recolorings with polylog(n) colors; not only is this an exponential improvement over the previous bound, but it also unveils a rather surprising phenomenon: The trade-off between the number of colors and recolorings is highly non-symmetric.
- For uniformly sparse graphs, we use low out-degree orientations to strengthen the above result by bounding the update time of the algorithm rather than the number of recolorings. Then, we further improve this result by introducing a new data structure that refines bounded out-degree edge orientations and is of independent interest
- …
