1,720,978 research outputs found
Labeled Nearest Neighbor Search and Metric Spanners via Locality Sensitive Orderings
Full text linkChan, Har-Peled, and Jones [SICOMP 2020] developed locality-sensitive
orderings (LSO) for Euclidean space. A -LSO is a collection
of orderings such that for every there is an
ordering , where all the points between and w.r.t.
are in the -neighborhood of either or . In essence, LSO
allow one to reduce problems to the -dimensional line. Later, Filtser and Le
[STOC 2022] developed LSO's for doubling metrics, general metric spaces, and
minor free graphs. For Euclidean and doubling spaces, the number of orderings
in the LSO is exponential in the dimension, which made them mainly useful for
the low dimensional regime. In this paper, we develop new LSO's for Euclidean,
, and doubling spaces that allow us to trade larger stretch for a much
smaller number of orderings. We then use our new LSO's (as well as the previous
ones) to construct path reporting low hop spanners, fault tolerant spanners,
reliable spanners, and light spanners for different metric spaces. While many
nearest neighbor search (NNS) data structures were constructed for metric
spaces with implicit distance representations (where the distance between two
metric points can be computed using their names, e.g. Euclidean space), for
other spaces almost nothing is known. In this paper we initiate the study of
the labeled NNS problem, where one is allowed to artificially assign labels
(short names) to metric points. We use LSO's to construct efficient labeled NNS
data structures in this model
Scattering and Sparse Partitions, and Their Applications
Full text linkA partition of a weighted graph G is (σ,τ,Δ)-sparse if every cluster has diameter at most Δ, and every ball of radius Δ/σ intersects at most τ clusters. Similarly, is (σ,τ,Δ)-scattering if instead for balls we require that every shortest path of length at most Δ/σ intersects at most τ clusters. Given a graph G that admits a (σ,τ,Δ)-sparse partition for all Δ > 0, Jia et al. [STOC05] constructed a solution for the Universal Steiner Tree problem (and also Universal TSP) with stretch O(τσ²log_τ n). Given a graph G that admits a (σ,τ,Δ)-scattering partition for all Δ > 0, we construct a solution for the Steiner Point Removal problem with stretch O(τ³σ³). We then construct sparse and scattering partitions for various different graph families, receiving many new results for the Universal Steiner Tree and Steiner Point Removal problems
On Strong Diameter Padded Decompositions
Full text linkGiven a weighted graph , a partition of is -bounded if
the diameter of each cluster is bounded by . A distribution over
-bounded partitions is a -padded decomposition if every ball of
radius is contained in a single cluster with probability at
least . The weak diameter of a cluster is measured
w.r.t. distances in , while the strong diameter is measured w.r.t. distances
in the induced graph . The decomposition is weak/strong according to the
diameter guarantee.
Formerly, it was proven that minor free graphs admit weak
decompositions with padding parameter , while for strong decompositions
only padding parameter was known. Furthermore, for the case of a graph
, for which the induced shortest path metric has doubling dimension
, a weak -padded decomposition was constructed, which is also known to
be tight. For the case of strong diameter, nothing was known.
We construct strong -padded decompositions for minor free graphs,
matching the state of the art for weak decompositions. Similarly, for graphs
with doubling dimension we construct a strong -padded decomposition,
which is also tight. We use this decomposition to construct strong
sparse cover scheme for such graphs. Our new
decompositions and cover have implications to approximating unique games, the
construction of light and sparse spanners, and for path reporting distance
oracles
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
On Strong Diameter Padded Decompositions
Full text linkGiven a weighted graph G=(V,E,w), a partition of V is Delta-bounded if the diameter of each cluster is bounded by Delta. A distribution over Delta-bounded partitions is a beta-padded decomposition if every ball of radius gamma Delta is contained in a single cluster with probability at least e^{-beta * gamma}. The weak diameter of a cluster C is measured w.r.t. distances in G, while the strong diameter is measured w.r.t. distances in the induced graph G[C]. The decomposition is weak/strong according to the diameter guarantee.
Formerly, it was proven that K_r free graphs admit weak decompositions with padding parameter O(r), while for strong decompositions only O(r^2) padding parameter was known. Furthermore, for the case of a graph G, for which the induced shortest path metric d_G has doubling dimension ddim, a weak O(ddim)-padded decomposition was constructed, which is also known to be tight. For the case of strong diameter, nothing was known.
We construct strong O(r)-padded decompositions for K_r free graphs, matching the state of the art for weak decompositions. Similarly, for graphs with doubling dimension ddim we construct a strong O(ddim)-padded decomposition, which is also tight. We use this decomposition to construct (O(ddim),O~(ddim))-sparse cover scheme for such graphs. Our new decompositions and cover have implications to approximating unique games, the construction of light and sparse spanners, and for path reporting distance oracles
On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and Other Applications
Full text linkGiven a metric space (X,d_X), a (β,s,Δ)-sparse cover is a collection of clusters ⊆ P(X) with diameter at most Δ, such that for every point x ∈ X, the ball B_X(x,Δ/β) is fully contained in some cluster C ∈ , and x belongs to at most s clusters in . Our main contribution is to show that the shortest path metric of every K_r-minor free graphs admits (O(r),O(r²),Δ)-sparse cover, and for every ε > 0, (4+ε,O(1/ε)^r,Δ)-sparse cover (for arbitrary Δ > 0). We then use this sparse cover to show that every K_r-minor free graph embeds into _∞^{Õ(1/ε)^{r+1}⋅log n} with distortion 3+ε (resp. into _∞^{Õ(r²)⋅log n} with distortion O(r)). Further, among other applications, this sparse cover immediately implies an algorithm for the oblivious buy-at-bulk problem in fixed minor free graphs with the tight approximation factor O(log n) (previously nothing beyond general graphs was known)
Scattering and Sparse Partitions, and their Applications
Full text linkA partition of a weighted graph is
-sparse if every cluster has diameter at most ,
and every ball of radius intersects at most clusters.
Similarly, is -scattering if instead for
balls we require that every shortest path of length at most
intersects at most clusters. Given a graph that admits a
-sparse partition for all , Jia et al. [STOC05]
constructed a solution for the Universal Steiner Tree problem (and also
Universal TSP) with stretch . Given a graph
that admits a -scattering partition for all ,
we construct a solution for the Steiner Point Removal problem with stretch
. We then construct sparse and scattering partitions for
various different graph families, receiving many new results for the Universal
Steiner Tree and Steiner Point Removal problems
A face cover perspective to embeddings of planar graphs
Full text linkIt was conjectured by Gupta et al. [Combinatorica04] that every planar graph can be embedded into with constant distortion. However, given an -vertex weighted planar graph, the best upper bound on the distortion is only , by Rao [SoCG99]. In this paper we study the case where there is a set of terminals, and the goal is to embed only the terminals into with low distortion. In a seminal paper, Okamura and Seymour [J.Comb.Theory81] showed that if all the terminals lie on a single face, they can be embedded isometrically into . The more general case, where the set of terminals can be covered by faces, was studied by Lee and Sidiropoulos [STOC09] and Chekuri et al. [J.Comb.Theory13]. The state of the art is an upper bound of by Krauthgamer, Lee and Rika [SODA19]. Our contribution is a further improvement on the upper bound to . Since every planar graph has at most faces, any further improvement on this result, will be a major breakthrough, directly improving upon Rao\u27s long standing upper bound. Moreover, it is well known that the flow-cut gap equals to the distortion of the best embedding into . Therefore, our result provides a polynomial time -approximation to the sparsest cut problem on planar graphs, for the case where all the demand pairs can be covered by faces.This version contains a new proof that every -decomposable metric admits a solution to the Lipshitz extension problem with stretch $O(β)
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
- …
