Arrow Research search

Author name cluster

Shiri Chechik

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.

38 papers
2 author rows

Possible papers

38

FOCS Conference 2024 Conference Paper

Improved Distance (Sensitivity) Oracles with Subquadratic Space

  • Davide Bilò
  • Shiri Chechik
  • Keerti Choudhary
  • Sarel Cohen
  • Tobias Friedrich 0001
  • Martin Schirneck

A distance oracle (DO) for a graph $G$ is a data structure that, when queried with vertices $s, t$, returns an estimate $\widehat{d}(s, t)$ of their distance in $G$. The oracle has stretch $(\alpha, \beta)$ if the estimate satisfies $d(s, t)\leqslant \widehat{d}(s, t)\leqslant \alpha\cdot d(s, t)+\beta$. An $f-\mathbf{edge}$ fault-tolerant distance sensitivity oracle $(f-\mathbf{DSO})$ additionally receives a set $F$ of up to $f$ edges and estimates the distance in $G-F$. Our first contribution is the design of new distance oracles with subquadratic space for undirected graphs. We show that introducing a small additive stretch $\beta > 0$ allows one to make the multiplicative stretch $\alpha$ arbitrarily small. This sidesteps a known lower bound of $\alpha\geqslant 3$ (for $\beta=0$ and subquadratic space) [Thorup & Zwick, JACM 2005]. We present a DO for graphs with edge weights in $[0, W]$ that, for any positive integer $\ell$ and any $c\in(0, \ell/2]$, has stretch $(1+\frac{1}{\ell}, 2W)$, space $\widetilde{O}(n^{2-\frac{c}{\ell}})$, and query time $O(n^{c})$, generalizing results by Agarwal and Godfrey [SODA 2013] to arbitrarily dense graphs. Our second contribution is a framework that turns an $(\alpha, \beta)- \mathbf{stretch}$ DO for unweighted graphs into an $(\alpha(1+\varepsilon), \beta)-\mathbf{stretch}. f-\mathbf{DSO}$ with sensitivity $f=o(\log(n)/\log\log n)$ retaining sub-quadratic space. This generalizes a result by Bilò, Chechik, Choudhary, Cohen, Friedrich, Krogmann, and Schirneck [TheoretiCS 2024]. Combining the framework with our new DO gives an $f-\mathbf{DSO}$ that, for any $\gamma\in(0, (\ell+1)/2]$, has stretch $((1+\frac{1}{\ell})(1+\varepsilon), 2)$, space $n^{2-\frac{\gamma}{(t+1)(f+1)}+o(1)}/\varepsilon^{f+2}$, and query time $\widetilde{O}(n^{\gamma}/\varepsilon^{2})$. This is the first $f-\mathbf{DSO}$ with subquadratic space, near-additive stretch, and sublinear query time.

Details

SODA Conference 2023 Conference Paper

Faster Deterministic Worst-Case Fully Dynamic All-Pairs Shortest Paths via Decremental Hop-Restricted Shortest Paths

  • Shiri Chechik
  • Tianyi Zhang 0008

Dynamic all-pairs shortest paths is a well-studied problem in the field of dynamic graph algorithms. More specifically, given a directed weighted graph G = ( V, E, ω) on n vertices which undergoes a sequence of vertex or edge updates, the goal is to maintain distances between any pair of vertices in V. In a classical work by [Demetrscu and Italiano, 2004], the authors showed that all-pairs shortest paths can be maintained deterministically in amortized Õ ( n 2 ) time 1, which is nearly optimal. For worst-case update time guarantees, so far the best randomized algorithm has Õ ( n 3-1/3 ) time [Abraham, Chechik, Krinninger, 2017], and the best deterministic algorithm needs Õ( n 3-2/7 ) time [Probst Gutenberg, Wulff-Nilsen, 2020]. We provide a faster deterministic worst-case update time of Õ ( n 3-20/61 ) for fully dynamic all-pairs shortest paths. To achieve this improvement, we study a natural variant of this problem where a hop constraint is imposed on shortest paths between vertices; that is, given a parameter h, the h -hop shortest path between any pair of vertices s, t ∈ V is a path from s to t with at most h edges whose total weight is minimized. As a result which might be of independent interest, we give a deterministic algorithm that maintains all-pairs h -hop shortest paths under vertex deletions in total update time Õ( n 3 h + Kn 2 n 2 ), where K bounds the total number of vertex deletions. * This publication is part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 803118 UncertainENV). 1 Õ (·) hides poly-log factors.

Details

FOCS Conference 2022 Conference Paper

Constant Approximation of Min-Distances in Near-Linear Time

  • Shiri Chechik
  • Tianyi Zhang 0008

In a weighed directed graph $G=(V, E, \omega)$ with m edges and n vertices, we are interested in its basic graph parameters such as diameter, radius and eccentricities, under the nonstandard measure of min-distance which is defined for every pair of vertices $u, v \in V$ as the minimum of the shortest path distances from u to v and from v to u. Similar to standard shortest paths distances, computing graph parameters exactly in terms of min-distances essentially requires $\tilde{\Omega}(m n)$ time under plausible hardness conjectures 1. Hence, for faster running time complexities we have to tolerate approximations. Abboud, Vassilevska Williams and Wang [SODA 2016] were the first to study min-distance problems, and they obtained constant factor approximation algorithms in acyclic graphs, with running time $\tilde{O}(m)$ and $\tilde{O}(m \sqrt{n})$ for diameter and radius, respectively. The time complexity of radius in acyclic graphs was recently improved to $\tilde{O}(m)$ by Dalirrooyfard and Kaufmann [ICALP 2021], but at the cost of an $O(\log n)$ approximation ratio. For general graphs, the authors of [DWV+, ICALP 2019] gave the first constant factor approximation algorithm for diameter, radius and eccentricities which runs in time $\tilde{O}(m \sqrt{n})$; besides, for the diameter problem, the running time can be improved to $\tilde{O}(m)$ while blowing up the approximation ratio to $O(\log n)$. A natural question is whether constant approximation and near-linear time can be achieved simultaneously for diameter, radius and eccentricities; so far this is only possible for diameter in the restricted setting of acyclic graphs. In this paper, we answer this question in the affirmative by presenting near-linear time algorithms for all three parameters in general graphs. 1 As usual, the $\tilde{O}(\cdot)$ notation hides poly-logarithmic factors in n

Details

SODA Conference 2021 Conference Paper

Incremental Single Source Shortest Paths in Sparse Digraphs

  • Shiri Chechik
  • Tianyi Zhang 0008

Given a directed graph G = ( V, E, ω ) with positive integer edge weights that undergoes a sequence of edge insertions, we are interested in maintaining approximate single-source shortest paths in the incremental graph G. In a very recent paper, [Gutenberg et al. , 2020] proposed a deterministic algorithm for this problem with Õ(n 2 log W ) total update time, where n = |V| and W denotes the maximum edge weight. When the underlying graph is super dense, namely, the total number of insertions m is, their upper bound is essentially optimal. For sparse graphs, the only known result is due to [Henzinger et al. , 2014], whose algorithm is randomized and works in Õ(mn 0. 9 log W ) total update time under the assumption of oblivious non-adaptive adversary. In this work, we provide two algorithms for this problem when the graph is sparse. The first one is a simple deterministic algorithm with Õ ( m 5/3 log W ) total update time. The second one is a randomized algorithm with Õ (( mn 1/2 + m 7/5 ) log W ) total update time, which improves over both previous results when m = O ( n 1. 42 ); moreover, this randomized algorithm plays against adaptive adversaries. Our algorithms are the first to break the O ( mn ) bound with adaptive adversaries for sparse graphs.

Details

SODA Conference 2021 Conference Paper

Optimal Girth Approximation for Dense Directed Graphs

  • Shiri Chechik
  • Gur Lifshitz

In this paper we provide a Õ ( n 2 ) time algorithm that computes a 2-multiplicative approximation of the girth of an n -node m -edge directed graph with non-negative edge weights. We also provide an additional algorithm that computes a 2-multiplicative approximation of the girth in time 1. Our results naturally provide algorithms for improved constructions of 4-roundtrip spanners, the analog of spanners in directed graphs. Our algorithm is optimal (up to a log n factor) for dense graphs with m = Θ( n 2 ). For comparison, previously, the best approximation ratio with a similar running time for dense graphs was O (log n log log n ) [1]. Moreover, unlike previous algorithms, our algorithm neither assumes integer weights, nor does it depend on the maximum edge weight of the graph.

Details

SODA Conference 2020 Conference Paper

Dynamic Low-Stretch Spanning Trees in Subpolynomial Time

  • Shiri Chechik
  • Tianyi Zhang 0008

Low-stretch spanning tree has been an important graphtheoretic object, as it is one of the building blocks for fast algorithms that solve symmetrically diagonally dominant linear systems, and a significant line of research has been devoted to finding constructions with optimal average stretch. In a very recent work by Goranci and Forster [STOC 2019], the authors initiated the study of low-stretch spanning trees in the dynamic setting, and they proposed a dynamic algorithm that maintains a spanning tree in amortized update time with subpolynomial stretch in an unweighted graph on n vertices undergoing edge insertions and deletions demanded by an oblivious adversary. Our main results are twofold. First, we substantially improve the update time of Goranci and Forster [STOC 2019] from to a subpolynomial of n o (1). Second, we generalize our result to weighted graphs under the decremental setting. As far as we know, this is the first non trivial dynamic algorithm for maintaining low-stretch spanning tree for weighted graphs.

Details

FOCS Conference 2019 Conference Paper

Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time

  • Shiri Chechik
  • Tianyi Zhang 0008

In the fully dynamic maximal independent set (MIS) problem our goal is to maintain an MIS in a given graph G while edges are inserted and deleted from the graph. The first non-trivial algorithm for this problem was presented by Assadi, Onak, Schieber, and Solomon [STOC 2018] who obtained a deterministic fully dynamic MIS with O(m 3/4 ) update time. Later, this was independently improved by Du and Zhang and by Gupta and Khan [arXiv 2018] to Õ(m 2/3 ) update time 1 Du and Zhang [arXiv 2018] also presented a randomized algorithm against an oblivious adversary with Õ(√m) update time. The current state of art is by Assadi, Onak, Schieber, and Solomon [SODA 2019] who obtained randomized algorithms against oblivious adversary with Õ(√n) and Õ(m 1/3 ) update times. In this paper, we propose a dynamic randomized algorithm against oblivious adversary with expected worst-case update time of O(log 4 n). As a direct corollary, one can apply the black-box reduction from a recent work by Bernstein, Forster, and Henzinger [SODA 2019] to achieve O(log 6 n) worst-case update time with high probability. This is the first dynamic MIS algorithm with very fast update time of poly-log.

Details

SODA Conference 2019 Conference Paper

Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model

  • Shiri Chechik
  • Doron Mukhtar

In this paper, we consider distributed coloring for planar graphs with a small number of colors. Our main result is an optimal (up to a constant factor) O (log n ) time algorithm for 6-coloring planar graphs. Our algorithm is based on a novel technique that in a nutshell detects small structures that can be easily colored given a proper coloring of the rest of the vertices and removes them from the graph until the graph contains a small enough number of edges. We believe this technique might be of independent interest. In addition, we present a lower bound for 4-coloring planar graphs that essentially shows that any algorithm (deterministic or randomized) for 4-coloring planar graphs requires Ω( n ) rounds. We therefore completely resolve the problems of 4-coloring and 6-coloring for planar graphs in the LOCAL model.

Details

AAAI Conference 2018 Conference Paper

Clustering Small Samples With Quality Guarantees: Adaptivity With One2all PPS

  • Edith Cohen
  • Shiri Chechik
  • Haim Kaplan

Clustering of data points is a fundamental tool in data analysis. We consider points X in a relaxed metric space, where the triangle inequality holds within a constant factor. A clustering of X is a partition of X defined by a set of points Q (centroids), according to the closest centroid. The cost of clustering X by Q is V (Q) = x∈X dxQ. This formulation generalizes classic k-means clustering, which uses squared distances. Two basic tasks, parametrized by k ≥ 1, are cost estimation, which returns (approximate) V (Q) for queries Q such that |Q| = k and clustering, which returns an (approximate) minimizer of V (Q) of size |Q| = k. When the data set X is very large, we seek efficient constructions of small samples that can act as surrogates for performing these tasks. Existing constructions that provide quality guarantees, however, are either worst-case, and unable to benefit from structure of real data sets, or make explicit strong assumptions on the structure. We show here how to avoid both these pitfalls using adaptive designs. The core of our design are the novel one2all probabilities, computed for a set M of centroids and α ≥ 1: The clustering cost of each Q with cost V (Q) ≥ V (M)/α can be estimated well from a sample of size O(α|M| −2 ). For cost estimation, we apply one2all with a bicriteria approximate M, while adaptively balancing |M| and α to optimize sample size per quality. For clustering, we present a wrapper that adaptively applies a base clustering algorithm to a sample S, using the smallest sample that provides the desired statistical guarantees on quality. We demonstrate experimentally the huge gains of using our adaptive instead of worst-case methods.

PDF Details

SODA Conference 2018 Conference Paper

Incremental Topological Sort and Cycle Detection in Expected Total Time

  • Aaron Bernstein
  • Shiri Chechik

In the incremental cycle detection problem edges are inserted to a directed graph (initially empty) and the algorithm has to report once a directed cycle is formed in the graph. A closely related problem to the incremental cycle detection is that of the incremental topological sort problem, in which edges are inserted to an acyclic graph and the algorithm has to maintain a valid topological sort on the vertices at all times. Both incremental cycle detection and incremental topological sort have a long history. The state of the art is a recent breakthrough of Bender, Fineman, Gilbert and Tarjan [TALG 2016], with two different algorithms with respective total update times of Õ ( n 2 ) and O ( m · min{ m 1/2, n 2/3 }). The two algorithms work for both incremental cycle detection and incremental topological sort. In this paper we introduce a novel technique that allows us to improve upon the state of the art for a wide range of graph sparsity. Our algorithms has a total expected update time of for both the incremental cycle detection and the topological sort problems.

Details

FOCS Conference 2018 Conference Paper

Near-Optimal Approximate Decremental All Pairs Shortest Paths

  • Shiri Chechik

In this paper we consider the decremental approximate all-pairs shortest paths (APSP) problem, where given a graph G the goal is to maintain approximate shortest paths between all pairs of nodes in G under a sequence of online adversarial edge deletions. We present a decremental APSP algorithm for undirected weighted graphs with (2+ε)k-1 stretch, O(mn 1/k +o(1) log(n W )) total update time and O(log log(n W)) query time for a fixed constant ε, where W is the maximum edge weight (assuming the minimum edge weight is 1) and k is any integer parameter. This is an exponential improvement both in the stretch and in the query time over previous works.

Details

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

(1 + ∊)-Approximate f -Sensitive Distance Oracles

  • Shiri Chechik
  • Sarel Cohen
  • Amos Fiat
  • Haim Kaplan

An f -Sensitive Distance Oracle with stretch a preprocesses a graph G ( V, E ) and produces a small data structure that is used to answer subsequent queries. A query is a triple consisting of a set F ⊂ E of at most f edges, and vertices s and t. The oracle answers a query (F, s. ,t) by returning a value d which is equal to the length of some path between s and t in the graph G\F (the graph obtained from G by discarding all edges in F). Moreover, d is at most a times the length of the shortest path between s and t in G \ F. The oracle can also construct a path between s and t in G\F of length d. To the best of our knowledge we give the first nontrivial f -sensitive distance oracle with fast query time and small stretch capable of handling multiple edge failures. Specifically, for any and a fixed ∊ > 0 our oracle answers queries ( F, s, t ) in time O (l) with (1 + ∊) stretch using a data structure of size n 2+0(1) For comparison, the naive alternative requires m f n 2 space for sublinear query time.

Details

SODA Conference 2017 Conference Paper

Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs

  • Shiri Chechik
  • Thomas Dueholm Hansen
  • Giuseppe F. Italiano
  • Veronika Loitzenbauer
  • Nikos Parotsidis

Connectivity related concepts are of fundamental interest in graph theory. The area has received extensive attention over four decades, but many problems remain unsolved, especially for directed graphs. A directed graph is 2-edge-connected (resp. , 2-vertex-connected) if the removal of any edge (resp. , vertex) leaves the graph strongly connected. In this paper we present improved algorithms for computing the maximal 2-edge- and 2- vertex-connected subgraphs of a given directed graph. These problems were first studied more than 35 years ago, with Õ ( mn ) time algorithms for graphs with m edges and n vertices being known since the late 1980s. In contrast, the same problems for undirected graphs are known to be solvable in linear time. Henzinger et al. [ICALP 2015] recently introduced O ( n 2 ) time algorithms for the directed case, thus improving the running times for dense graphs. Our new algorithms run in time O ( m 3/2 ), which further improves the running times for sparse graphs. The notion of 2-connectivity naturally generalizes to k -connectivity for k > 2. For constant values of k, we extend one of our algorithms to compute the maximal k -edge-connected in time O ( m 3/2 log n ), improving again for sparse graphs the best known algorithm by Henzinger et al. [ICALP 2015] that runs in O ( n 2 log n ) time.

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

FOCS Conference 2016 Conference Paper

Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time

  • Shiri Chechik
  • Thomas Dueholm Hansen
  • Giuseppe F. Italiano
  • Jakub Lacki
  • Nikos Parotsidis

We present randomized algorithms with a total update time of Õ(m √n) for the problems of decremental single source reachability and decremental strongly connected components on directed graphs. This improves recent breakthrough results of Henzinger, Krinninger and Nanongkai [STOC 14, ICALP 15]. In addition, our algorithms are arguably simpler.

Details

STOC Conference 2016 Conference Paper

Deterministic decremental single source shortest paths: beyond the o(mn) bound

  • Aaron Bernstein
  • Shiri Chechik

In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph G and a source node s the goal is to maintain shortest paths between s and all other nodes in G under a sequence of online adversarial edge deletions. In their seminal work, Even and Shiloach [JACM 1981] presented an exact solution to the problem with only O ( mn ) total update time over all edge deletions. Their classic algorithm was the best known result for the decremental SSSP problem for three decades, even when approximate shortest paths are allowed. The first improvement over the Even-Shiloach algorithm was given by Bernstein and Roditty [SODA 2011], who for the case of an unweighted and undirected graph presented an approximate (1+) algorithm with constant query time and a total update time of O ( n 2+ O (1/√log n ) ). This work triggered a series of new results, culminating in a recent breakthrough of Henzinger, Krinninger and Nanongkai [FOCS 14], who presented a -approximate algorithm whose total update time is near linear O ( m 1+ O (1/√log n ) ). In this paper they posed as a major open problem the question of derandomizing their result. In fact, all known improvements over the Even-Shiloach algorithm are randomized. All these algorithms maintain some truncated shortest path trees from a small subset of nodes. While in the randomized setting it is possible to “hide” these nodes from the adversary, in the deterministic setting this is impossible: the adversary can delete all edges touching these nodes, thus forcing the algorithm to choose a new set of nodes and incur a new computation of shortest paths. In this paper we present the first deterministic decremental SSSP algorithm that breaks the Even-Shiloach bound of O ( mn ) total update time, for unweighted and undirected graphs. Our algorithm is (1 + є) approximate and achieves a total update time of Õ( n 2 ). Our algorithm can also achieve the same bounds in the incremental setting. It is worth mentioning that for dense instances where m = Ω( n 2 − 1/√log( n ) ), our algorithm is also faster than all existing randomized algorithms.

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

TCS Journal 2015 Journal Article

Fault tolerant additive and ( μ, α ) -spanners

  • Gilad Braunschvig
  • Shiri Chechik
  • David Peleg
  • Adam Sealfon

Graph spanners are sparse subgraphs that preserve the distances of the original graph up to some approximation ratio (the spanner's stretch). A number of algorithms are known for constructing sparse spanners with small multiplicative or additive stretch. Recently, algorithms were introduced for constructing fault-tolerant multiplicative spanners of general graphs. This paper addresses the analogous problem of constructing fault tolerant additive and ( μ, α ) -spanners for general graphs, and presents a number of (deterministic and randomized) construction algorithms for such spanners.

Details DOI

TCS Journal 2015 Journal Article

The fault-tolerant capacitated K-center problem

  • Shiri Chechik
  • David Peleg

The capacitated K-center (CKC) problem calls for locating K service centers in the vertices of a given weighted graph, and assigning each vertex as a client to one of the centers, where each service center has a limited service capacity and thus may be assigned at most L clients, so as to minimize the maximum distance from a vertex to its assigned service center. This paper studies the fault-tolerant version of this problem, where one or more service centers might fail simultaneously. We consider two variants of the problem. The first is the α-fault-tolerant capacitated K-center ( α - F T - C K C ) problem. In this version, after the failure of some centers, all nodes are allowed to be reassigned to alternate centers. The more conservative version of this problem, hereafter referred to as the α-fault-tolerant conservative capacitated K-center ( α - F T - C K C ) problem, is similar to the α - F T - C K C problem, except that after the failure of some centers, only the nodes that were assigned to those centers before the failure are allowed to be reassigned to other centers. We present polynomial time algorithms that yield 9-approximation for the α - F T - C K C problem and 17-approximation for the α - F T - C K C problem.

Details DOI

SODA Conference 2014 Conference Paper

Better Approximation Algorithms for the Graph Diameter

  • Shiri Chechik
  • Daniel H. Larkin
  • Liam Roditty
  • Grant Schoenebeck
  • Robert Endre Tarjan
  • Virginia Vassilevska Williams

The diameter is a fundamental graph parameter and its computation is necessary in many applications. The fastest known way to compute the diameter exactly is to solve the All-Pairs Shortest Paths (APSP) problem. In the absence of fast algorithms, attempts were made to seek fast algorithms that approximate the diameter. In a seminal result Aingworth, Chekuri, Indyk and Motwani [SODA'96 and SICOMP'99] designed an algorithm that computes in time an estimate for the diameter D in directed graphs with nonnegative edge weights, such that ⌊⅔ · D ⌋ – ( M – 1) ≤ ≤ D, where M is the maximum edge weight in the graph. In recent work, Roditty and Vassilevska W. [STOC 13] gave a Las Vegas algorithm that has the same approximation guarantee but improves the (expected) runtime to. Roditty and Vassilevska W. also showed that unless the Strong Exponential Time Hypothesis fails, no ( n 2− ∊ ) time algorithm for sparse unweighted undirected graphs can achieve an approximation ratio better than. Thus their algorithm is essentially tight for sparse unweighted graphs. For weighted graphs however, the approximation guarantee can be meaningless, as M can be arbitrarily large. In this paper we exhibit two algorithms that achieve a genuine -approximation for the diameter, one running in time, and one running in time. Furthermore, our algorithms are deterministic, and thus we present the first deterministic (2 – ∊ )-approximation algorithm for the diameter that takes subquadratic time in sparse graphs. In addition, we address the question of obtaining an additive c -approximation for the diameter, i. e. an estimate such that D – c ≤ ≤ D. An extremely simple time algorithm achieves an additive n ∊ -approximation; no better results are known. We show that for any ∊ > 0, getting an additive n ∊ -approximation algorithm for the diameter running in ( n 2− δ ) time for any δ > 2 ∊ would falsify the Strong Exponential Time Hypothesis. Thus the simple algorithm is probably essentially tight for sparse graphs, and moreover, obtaining a subquadratic time additive c -approximation for any constant c is unlikely. Finally, we consider the problem of computing the eccentricities of all vertices in an undirected graph, i. e. the largest distance from each vertex. Roditty and Vassilevska W. [STOC 13] show that in time, one can compute for each v ∊ V in an undirected graph, an estimate ∊( v ) for the eccentricity ∊( v ) such that max { R, · ∊( v )} ≤ ∊( v ) ≤ min { D, · ∊( v )} where R = min v ∊(v) is the radius of the graph. Here we improve the approximation guarantee by showing that a variant of the same algorithm can achieve estimates ∊ ′ ( v ) with · ∊( v ) ≤ ∊′ ( v ) ≤ ∊( v ).

Details

TCS Journal 2014 Journal Article

Robust fault tolerant uncapacitated facility location

  • Shiri Chechik
  • David Peleg

In the uncapacitated facility location problem, given a graph, a set of demands and opening costs, it is required to find a set of facilities R, so as to minimize the sum of the cost of opening the facilities in R and the cost of assigning all node demands to open facilities. This paper concerns the robust fault-tolerant version of the uncapacitated facility location problem (RFTFL). In this problem, one or more facilities might fail, and each demand should be supplied by the closest open facility that did not fail. It is required to find a set of facilities R, so as to minimize the sum of the cost of opening the facilities in R and the cost of assigning all node demands to open facilities that did not fail, after the failure of up to α facilities. We present a polynomial time algorithm that yields a 6. 464-approximation for this problem with at most one failure and a 1. 488 + 7. 464 α -approximation for the problem with at most α failures for a fixed α > 1. We also show that the RFTFL problem is NP-hard even on trees, and even in the case of a single failure.

Details DOI

SODA Conference 2013 Conference Paper

New Additive Spanners

  • Shiri Chechik

This paper considers additive and purely additive spanners. We present a new purely additive spanner of size Õ ( n 7/5 ) with additive stretch 4. This construction fills in the gap between the two existing constructions for purely additive spanners, one for 2-additive spanner of size O ( n 3/2 ) and the other for 6-additive spanner of size O ( n 4/3 ), and thus answers a main open question in this area. In addition, we present a construction for additive spanners with Õ ( n 1+δ ) edges and additive stretch of O ( n 1/2–3δ/2 ) for any 3 / 17 ≤ δ < 1 / 3, improving the stretch of the existing constructions from O ( n 1–3δ ) to. Finally, we show that our (1, n 1/2–3δ/2 )-spanner construction can be tweaked to give a sublinear additive spanner of size O ( n 1+3/17 ) with additive stretch.

Details