Arrow Research search

Author name cluster

Ittai Abraham

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers
1 author row

Possible papers

19

SODA Conference 2018 Conference Paper

Ramsey Spanning Trees and their Applications

  • Ittai Abraham
  • Shiri Chechik
  • Michael Elkin
  • Arnold Filtser
  • Ofer Neiman

The metric Ramsey problem asks for the largest subset S of a metric space that can be embedded into an ultrametric (more generally into a Hilbert space) with a given distortion. Study of this problem was motivated as a non-linear version of Dvoretzky theorem. Mendel and Naor [MN07] devised the so called Ramsey Partitions to address this problem, and showed the algorithmic applications of their techniques to approximate distance oracles and ranking problems. In this paper we study the natural extension of the metric Ramsey problem to graphs, and introduce the notion of Ramsey Spanning Trees. We ask for the largest subset S ⊆ V of a given graph G = ( V, E ), such that there exists a spanning tree of G that has small stretch for S. Applied iteratively, this provides a small collection of spanning trees, such that each vertex has a tree providing low stretch paths to all other vertices. The union of these trees serves as a special type of spanner, a tree-padding spanner. We use this spanner to devise the first compact stateless routing scheme with O (1) routing decision time, and labels which are much shorter than in all currently existing schemes. We first revisit the metric Ramsey problem, and provide a new deterministic construction. We prove that for every k, any n -point metric space has a subset S of size at least n 1–1/ k which embeds into an ultrametric with distortion 8 k. We use this result to obtain the state-of-the-art deterministic construction of a distance oracle. Building on this result, we prove that for every k, any n -vertex graph G = ( V, E ) has a subset S of size at least n 1–1/ k, and a spanning tree of G, that has stretch O ( k log log n ) between any point in S and any point in V.

Details

SODA Conference 2017 Conference Paper

Fully dynamic all-pairs shortest paths with worst-case update-time revisited

  • Ittai Abraham
  • Shiri Chechik
  • Sebastian Forster

We revisit the classic problem of dynamically maintaining shortest paths between all pairs of nodes of a directed weighted graph. The allowed updates are insertions and deletions of nodes and their incident edges. We give worst- case guarantees on the time needed to process a single update (in contrast to related results, the update time is not amortized over a sequence of updates). Our main result is a simple randomized algorithm that for any parameter c > 1 has a worst-case update time of O ( cn 2 + 2/3 log 4/3 n ) and answers distance queries correctly with probability 1 — 1/n c, against an adaptive online adversary if the graph contains no negative cycle. The best deterministic algorithm is by Thorup [STOC 2005] with a worst-case update time of Õ ( n 2+3/4 ) and assumes non-negative weights. This is the first improvement for this problem for more than a decade. Conceptually, our algorithm shows that randomization along with a more direct approach can provide better bounds.

Details

SODA Conference 2016 Conference Paper

On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs

  • Ittai Abraham
  • Shiri Chechik
  • Daniel Delling
  • Andrew V. Goldberg
  • Renato F. Werneck

Given a base weighted planar graph G input on n nodes and parameters M, ∊ we present a dynamic distance oracle with 1 + ∊ stretch and worst case update and query costs of ∊ –3 M 4 · poly-log( n ). We allow arbitrary edge weight updates as long as the shortest path metric induced by the updated graph has stretch of at most M relative to the shortest path metric of the base graph G input. For example, on a planar road network, we can support fast queries and dynamic traffic updates as long as the shortest path from any source to any target (including using arbitrary detours) is between, say, 80 and 3 miles-per-hour. As a warm-up we also prove that graphs of bounded treewidth have exact distance oracles in the dynamic edge model. To the best of our knowledge, this is the first dynamic distance oracle for a non-trivial family of dynamic changes to planar graphs with worst case costs of o ( n 1/2 ) both for query and for update operations.

Details

FOCS Conference 2016 Conference Paper

On Fully Dynamic Graph Sparsifiers

  • Ittai Abraham
  • David Durfee
  • Ioannis Koutis
  • Sebastian Forster
  • Richard Peng

We initiate the study of fast dynamic algorithms for graph sparsification problems and obtain fully dynamic algorithms, allowing both edge insertions and edge deletions, that take polylogarithmic time after each update in the graph. Our three main results are as follows. First, we give a fully dynamic algorithm for maintaining a (1 ± ϵ)-spectral sparsifier with amortized update time poly(log n, ϵ -1 ). Second, we give a fully dynamic algorithm for maintaining a (1 ± ϵ)-cut sparsifier with worst-case update time poly(log n, ϵ -1 ). Both sparsifiers have size n · poly(log n, ϵ -1 ). Third, we apply our dynamic sparsifier algorithm to obtain a fully dynamic algorithm for maintaining a (1 - ϵ)-approximation to the value of the maximum flow in an unweighted, undirected, bipartite graph with amortized update time poly(log n, ϵ -1 ).

Details

STOC Conference 2014 Conference Paper

Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs

  • Ittai Abraham
  • Cyril Gavoille
  • Anupam Gupta 0001
  • Ofer Neiman
  • Kunal Talwar

We prove that any graph excluding K r as a minor has can be partitioned into clusters of diameter at most Δ while removing at most O ( r/ Δ) fraction of the edges. This improves over the results of Fakcharoenphol and Talwar, who building on the work of Klein, Plotkin and Rao gave a partitioning that required to remove O ( r 2 /Δ) fraction of the edges. Our result is obtained by a new approach that relates the topological properties (excluding a minor) of a graph to its geometric properties (the induced shortest path metric). Specifically, we show that techniques used by Andreae in his investigation of the cops and robbers game on graphs excluding a fixed minor, can be used to construct padded decompositions of the metrics induced by such graphs. In particular, we get probabilistic partitions with padding parameter O ( r ) and strong-diameter partitions with padding parameter O ( r 2 ) for K r -free graphs, O ( k ) for treewidth- k graphs, and O (log g ) for graphs with genus g .

Details

SODA Conference 2010 Conference Paper

Highway Dimension, Shortest Paths, and Provably Efficient Algorithms

  • Ittai Abraham
  • Amos Fiat
  • Andrew V. Goldberg
  • Renato F. Werneck

Computing driving directions has motivated many shortest path heuristics that answer queries on continental scale networks, with tens of millions of intersections, literally instantly, and with very low storage overhead. In this paper we complement the experimental evidence with the first rigorous proofs of efficiency for many of the heuristics suggested over the past decade. We introduce the notion of highway dimension and show how low highway dimension gives a unified explanation for several seemingly different algorithms.

Details

SODA Conference 2009 Conference Paper

On low dimensional local embeddings

  • Ittai Abraham
  • Yair Bartal
  • Ofer Neiman

We study the problem of embedding metric spaces into low dimensional ℓ p spaces while faithfully preserving distances from each point to its k nearest neighbors. We show that any metric space can be embedded into with k -local distortion of O ((log k )/ p ). We also show that any ultrametric can be embedded into with k -local distortion 1 + ∊. Our embedding results have immediate applications to local Distance Oracles. We show how to preprocess a graph in polynomial time to obtain a data structure of O ( nk 1/t log 2 k ) bits, such that distance queries from any node to its k nearest neighbors can be answered with stretch O ( t ).

Details

FOCS Conference 2008 Conference Paper

Nearly Tight Low Stretch Spanning Trees

  • Ittai Abraham
  • Yair Bartal
  • Ofer Neiman

We prove that any graph G with n points has a distribution T over spanning trees such that for any edge (u, v) the expected stretch E T~T [d T (u, nu)/d G (u, nu)] is bounded by Otilde(log n). Our result is obtained via a new approach of building "highways" between portals and a new strong diameter probabilistic decomposition theorem.

Details

STOC Conference 2007 Conference Paper

Local embeddings of metric spaces

  • Ittai Abraham
  • Yair Bartal
  • Ofer Neiman

In many application areas, complex data sets are often representedby some metric space and metric embedding is used to provide a more structured representation of the data. In many of these applications much greater emphasis is put on the preserving the local structure of the original space than on maintaining its complete structure. This is also the case in some networking applications where "small world" phenomena in communication patterns has been observed. Practical study of embedding has indeed involved with finding embeddings with this property. In this paper we initiate thestudy of local embeddings of metric spaces and provide embeddings with distortion depending solely on the local structureof the space.

Details

FOCS Conference 2005 Conference Paper

Metric Embeddings with Relaxed Guarantees

  • Ittai Abraham
  • Yair Bartal
  • T. -H. Hubert Chan
  • Kedar Dhamdhere
  • Anupam Gupta 0001
  • Jon M. Kleinberg
  • Ofer Neiman
  • Aleksandrs Slivkins

We consider the problem of embedding finite metrics with slack: we seek to produce embeddings with small dimension and distortion while allowing a (small) constant fraction of all distances to be arbitrarily distorted. This definition is motivated by recent research in the networking community, which achieved striking empirical success at embedding Internet latencies with low distortion into low-dimensional Euclidean space, provided that some small slack is allowed. Answering an open question of Kleinberg, Slivkins, and Wexler (2004), we show that provable guarantees of this type can in fact be achieved in general: any finite metric can be embedded, with constant slack and constant distortion, into constant-dimensional Euclidean space. We then show that there exist stronger embeddings into /spl lscr//sub 1/ which exhibit gracefully degrading distortion: these is a single embedding into /spl lscr//sub 1/ that achieves distortion at most O(log 1//spl epsi/) on all but at most an /spl epsi/ fraction of distances, simultaneously for all /spl epsi/ > 0. We extend this with distortion O(log 1//spl epsi/)/sup 1/p/ to maps into general /spl lscr//sub p/, p /spl ges/ 1 for several classes of metrics, including those with bounded doubling dimension and those arising from the shortest-path metric of a graph with an excluded minor. Finally, we show that many of our constructions are tight, and give a general technique to obtain lower bounds for /spl epsi/-slack embeddings from lower bounds for low-distortion embeddings.

Details