Arrow Research search

Author name cluster

Robert Endre Tarjan

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.

65 papers
2 author rows

Possible papers

65

FOCS Conference 2024 Conference Paper

Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps

  • Bernhard Haeupler
  • Richard Hladík
  • Václav Rozhon
  • Robert Endre Tarjan
  • Jakub Tetek

This paper proves that Dijkstra's shortest-path algorithm is universally optimal in both its running time and number of comparisons when combined with a sufficiently efficient heap data structure. Universal optimality is a powerful beyond-worst-case performance guarantee for graph algorithms that informally states that a single algorithm performs as well as possible for every single graph topology. We give the first application of this notion to any sequential algorithm. We design a new heap data structure with a working-set property guaranteeing that the heap takes advantage of locality in heap operations. Our heap matches the optimal (worst-case) bounds of Fibonacci heaps but also provides the beyond-worst-case guarantee that the cost of extracting the minimum element is merely logarithmic in the number of elements inserted after it instead of logarithmic in the number of all elements in the heap. This makes the extraction of recently added elements cheaper. We prove that our working-set property guarantees universal optimality for the problem of ordering vertices by their distance from the source vertex: The sequence of heap operations generated by any run of Dijkstra's algorithm on a fixed graph possesses enough locality that one can couple the number of comparisons performed by any heap with our working-set bound to the minimum number of comparisons required to solve the distance ordering problem on this graph for a worst-case choice of arc lengths.

Details

SODA Conference 2022 Conference Paper

Simulating a stack using queues

  • Haim Kaplan
  • Robert Endre Tarjan
  • Or Zamir
  • Uri Zwick

It is well known that a queue can be simulated by two stacks using a constant number of stack operations per queue operation. In this paper we consider the forgotten converse problem of simulating a stack using several queues. We consider several variants of this problem. For the offline variant, we obtain a tight upper and lower bounds for the worst-case number of queue operations needed to simulate a sequence of n stack operations using k queues. For the online variant, when the number of queues k is constant, and n is the maximum number of items in the stack at any given time, we obtain tight Θ( n 1/ k ) upper and lower bounds on the worst-case and amortized number of queue operations needed to simulate one stack operation. When k is allowed to grow with n, we prove an upper bound of O ( n 1/ k + log k n ) and a lower bound of on the amortized number of queue operations per stack operation. We also prove an upper bound of O ( kn 1/ k ) and a lower bound of Ω( n 1/ k + log k n ) on the worst-case number of queue operations per stack operation. We also show that the specific but interesting sequence of n pushes followed by n pops can be implemented much faster using a total number of only Θ( n log k n ) queue operations, for every k ≥ 2, an amortized number of Θ(log k n ) queue operations per stack operation, and this bound is tight. On the other hand, we show that the same sequence requires at least Ω( n 1/ k ) queue operations per stack operation in the worst case.

Details

SODA Conference 2019 Conference Paper

A New Path from Splay to Dynamic Optimality

  • Caleb C. Levy
  • Robert Endre Tarjan

Consider the task of performing a sequence of searches in a binary search tree. After each search, an algorithm is allowed to arbitrarily restructure the tree, at a cost proportional to the amount of restructuring performed. The cost of an execution is the sum of the time spent searching and the time spent optimizing those searches with restructuring operations. This notion was introduced by Sleator and Tarjan in 1985 [27], along with an algorithm and a conjecture. The algorithm, Splay, is an elegant procedure for performing adjustments while moving searched items to the top of the tree. The conjecture, called dynamic optimality, is that the cost of splaying is always within a constant factor of the optimal algorithm for performing searches. The conjecture stands to this day. We offer the first systematic proposal for settling the dynamic optimality conjecture. At the heart of our methods is what we term a simulation embedding: a mapping from executions to lists of keys that induces a target algorithm to simulate the execution. We build a simulation embedding for Splay by inducing it to perform arbitrary subtree transformations, and use this to show that if the cost of splaying a sequence of items is an upper bound on the cost of splaying every subsequence thereof, then Splay is dynamically optimal. We call this the subsequence property. Building on this machinery, we show that if Splay is dynamically optimal, then with respect to optimal costs, its additive overhead is at most linear in the sum of initial tree size and number of requests. As a corollary, the subsequence property is also a necessary condition for dynamic optimality. The subsequence property also implies both the traversal [27] and deque [30] conjectures. The notions of simulation embeddings and bounding additive overheads should be of general interest in competitive analysis. For readers especially interested in dynamic optimality, we provide an outline of a proof that a lower bound on search costs by Wilber [32] has the subsequence property, and extensive suggestions for adapting this proof to Splay.

Details

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

SODA Conference 2014 Conference Paper

Disjoint Set Union with Randomized Linking

  • Ashish Goel
  • Sanjeev Khanna
  • Daniel H. Larkin
  • Robert Endre Tarjan

A classic result in the analysis of data structures is that path compression with linking by rank solves the disjoint set union problem in almost-constant amortized time per operation. Recent experiments suggest that in practice, a naïve linking method works just as well if not better than linking by rank, in spite of being theoretically inferior. How can this be? We prove that randomized linking is asymptotically as efficient as linking by rank. This result provides theory that matches the experiments, which implicitly do randomized linking as a result of the way the input instances are generated.

Details

FOCS Conference 2012 Conference Paper

A Weight-Scaling Algorithm for Min-Cost Imperfect Matchings in Bipartite Graphs

  • Lyle Ramshaw
  • Robert Endre Tarjan

Call a bipartite graph G = (X, Y; E) balanced when |X| = |Y |. Given a balanced bipartite graph G with edge costs, the assignment problem asks for a perfect matching in G of minimum total cost. The Hungarian Method can solve assignment problems in time O(mn+n 2 log n), where n: = |X| = |Y | and m: = |E|. If the edge weights are integers bounded in magnitude by C >; 1, then algorithms using weight scaling, such as that of Gabow and Tarjan, can lower the time to O(m√n log(nC)). There are important applications in which G is unbalanced, with |X| ≠ |Y |, and we require a min-cost matching of size r: = min(|X|, |Y |) or, more generally, of some specified size s ≤ r. The Hungarian Method extends easily to find such a matching in time O(ms + s 2 log r), but weightscaling algorithms do not extend so easily. We introduce new machinery to find such a matching in time O(m√s log(sC)) via weight scaling. Our results provide some insight into the design space of efficient weight-scaling matching algorithms.

Details

STOC Conference 2012 Conference Paper

Strict fibonacci heaps

  • Gerth Stølting Brodal
  • George Lagogiannis
  • Robert Endre Tarjan

We present the first pointer-based heap implementation with time bounds matching those of Fibonacci heaps in the worst case. We support make-heap, insert, find-min, meld and decrease-key in worst-case O(1) time, and delete and delete-min in worst-case O(lg n) time, where n is the size of the heap. The data structure uses linear space. A previous, very complicated, solution achieving the same time bounds in the RAM model made essential use of arrays and extensive use of redundant counter schemes to maintain balance. Our solution uses neither. Our key simplification is to discard the structure of the smaller heap when doing a meld. We use the pigeonhole principle in place of the redundant counter mechanism.

Details

STOC Conference 2002 Conference Paper

Meldable heaps and boolean union-find

  • Haim Kaplan
  • Nira Shafrir
  • Robert Endre Tarjan

In the classical meldable heap data type we maintain an item-disjoint collection of heaps under the operations find-min , insert , delete , decrease-key , and meld . In the usual definition decrease-key and delete get the item and the heap containing it as parameters. We consider the modified problem where decrease-key and delete get only the item but not the heap containing it. We show that for this problem one of the operations find-min , decrease-key , or meld must take non-constant time. This is in contrast with the original data type in which data structures supporting all these three operations in constant time are known (both in an amortized and a worst-case setting).To establish our results for meldable heaps we consider a weaker version of the union-find problem that is of independent interest, which we call Boolean union-find . In the Boolean union-find problem the find operation is a binary predicate that gets an item x and a set A and answers positively if and only if χ ε A . We prove that the lower bounds which hold for union-find in the cell probe model hold for Boolean union-find as well.We also suggest new heap data structures implementing the modified meldable heap data type that are based on redundant binary counters. Our data structures have good worst-case bounds. The best of our data structures matches the worst-case lower bounds which we establish for the problem. The simplest of our data structures is an interesting generalization of binomial queues.

Details

FOCS Conference 1994 Conference Paper

Tractability of parameterized completion problems on chordal and interval graphs: Minimum Fill-in and Physical Mapping

  • Haim Kaplan
  • Ron Shamir
  • Robert Endre Tarjan

We study the parameterized complexity of several NP-Hard graph completion problems: The minimum fill-in problem is to decide if a graph can be triangulated by adding at most k edges. We develop an O(k/sup 5/ mn+f(K)) algorithm for the problem on a graph with n vertices and m edges. In particular, this implies that the problem is fixed parameter tractable (FPT). proper interval graph completion problems, motivated by molecular biology, ask for adding edges in order to obtain a proper interval graph, so that a parameter in that graph does not exceed k. We show that the problem is FPT when k is the number of added edges. For the problem where k is the clique size, we give an O(f(k)n/sup k-1/) algorithm, so it is polynomial for fixed k. On the other hand, we prove its hardness in the parameterized hierarchy, so it is probably not FPT. Those results are obtained even when a set of edges which should not be added is given. That set can be given either explicitly or by a proper vertex coloring which the added edges should respect. >

Details

FOCS Conference 1992 Conference Paper

Data Structural Bootstrapping, Linear Path Compression, and Catenable Heap Ordered Double Ended Queues

  • Adam L. Buchsbaum
  • Rajamani Sundar
  • Robert Endre Tarjan

The authors provide an efficient implementation of catenable mindeques. To prove that the resulting data structure achieves constant amortized time per operation, they consider order preserving path compression. They prove a linear bound on deque ordered spine-only path compression, a case of order persevering path compression employed by the data structure. >

Details

FOCS Conference 1988 Conference Paper

Dynamic Perfect Hashing: Upper and Lower Bounds

  • Martin Dietzfelbinger
  • Anna R. Karlin
  • Kurt Mehlhorn
  • Friedhelm Meyer auf der Heide
  • Hans Rohnert
  • Robert Endre Tarjan

A randomized algorithm is given for the dictionary problem with O(1) worst-case time for lookup and O(1) amortized expected time for insertion and deletion. An Omega (log n) lower bound is proved for the amortized worst-case time complexity of any deterministic algorithm in a class of algorithms encompassing realistic hashing-based schemes. If the worst-case lookup time is restricted to k, then the lower bound for insertion becomes Omega (kn/sup 1/k/). >

Details

FOCS Conference 1987 Conference Paper

Correction to "A Linear-Time Algorithm for Triangulating Simple Polygons"

  • Robert Endre Tarjan
  • Christopher J. Van Wyk

In "A linear-time algorithm for triangulating a simple polygon" [Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (1986), 380-388. 486], the analysis showing that the authors' triangulation algorithm runs in linear time is incorrect, and indeed the algorithm does not run in linear time in the worst case. So far they have been unable to obtain a linear-time algorithm for the triangulation problem. They have been able to obtain an O(n loglogn)-time algorithm, however. The details are described in "An O(n loglogn)-Time Algorithm for Triangulating a Simple Polygon, " SIAM Journal on Computing 17, 1 (February, 1988), to appear.

Details

FOCS Conference 1984 Conference Paper

Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms

  • Michael L. Fredman
  • Robert Endre Tarjan

In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps), extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary deletion from an n-item heap in 0(log n) amortized time and all other standard heap operations in 0(1) amortized time. Using F-heaps we are able to obtain improved running times for several network optimization algorithms.

Details

FOCS Conference 1984 Conference Paper

Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time (Extended Summary)

  • Robert Endre Tarjan
  • Uzi Vishkin

We propose a new algorithm for finding the blocks (biconnected components) of an undirected graph. A serial implementation runs in 0[n+m] time and space on a graph of n vertices and m edges. A parallel implmentation runs in 0[log n] time and 0[n+m] space using 0[n+m] processors on a concurrent-read, concurrent-write parallel RAM. An alternative implementation runs in 0[n/sup 2/p] time and 0[n/sup 2/] space using any number p ⩽ n/sup 2/log/sup 2/-n of processors, on a concurrent-read, exclusive-write parallel RAM. The latter algorithm has optimal speedup, assuming an adjacency matrix representation of the input. A general algorithmic technique which simplifies and improve computation of various functions on tress is introduced. This technique typically requires 0(log n) time using 0(n) space on an exclusive-read exclusive-write parallel RAM.

Details

FOCS Conference 1980 Conference Paper

Biased 2-3 Trees

  • Samuel W. Bent
  • Daniel Dominic Sleator
  • Robert Endre Tarjan

We describe a new data structure for maintaining collections of weighted items. The access time for an item of weight w in a collection of total weight W is proportional to log(W/w) in the worst case (which is optimal in a certain sense), and several other useful operations can be made to work just, as fast. The data structure is simpler than previous proposals, but the running time must be amortized over a sequence of operations to achieve the time bounds.

Details

FOCS Conference 1979 Conference Paper

Efficient Algorithms for Simple Matroid Intersection Problems

  • Harold N. Gabow
  • Robert Endre Tarjan

Given a matroid, where each element has a realvalued cost and is colored red or green; we seek a minimum cost base with exactly q red elements. This is a simple case of the matroid intersection problem. A general algorithm is presented. Its efficiency is illustrated in the special case of finding a minimum spanning tree with q red edges; the time is O(m log log n + n α (n, n) log n). Efficient algorithms are also given for job scheduling matroids and partition matroids. An algorithm is given for finding a minimum spanning tree where a vertex r has prespecified degree; it shows this problem is equivalent to finding a minimum spanning tree, without the degree constraint. An algorithm is given for finding a minimum spanning tree on a directed graph, where the given root r has prespecified degree; the time is O(m log n), the same as for the problem without the degree constraint.

Details

FOCS Conference 1977 Conference Paper

Application of a Planar Separator Theorem

  • Richard J. Lipton
  • Robert Endre Tarjan

Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only O(√n) vertices. This separator theorem, in combination with a divide-and-conquer strategy, leads to many new complexity results for planar graph problems. This paper describes some of these results.

Details