Linear Data Structures for Fast Ray-Shooting amidst Convex (2009)
Haim Kaplan, Natan Rubin, Micha Sharir
We consider the problem of ray shooting in a three-dimensional scene consisting of k (possibly intersecting) convex polyhedra with a total of n facets. That is, we want to preprocess them into a data...
Noga Alon, Haim Kaplan, Gabriel Nivasch, Shakhar Smorodinsky
Abstract. We construct weak ɛ-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1-nets of size O(rα(r)), where...
Tighter Estimation using Bottom-k Sketches (2009)
Summaries of massive data sets support approximate query processing over the original data. A basic aggregate over a set of records is the weight of subpopulations specified as a predicate over...
Haim Kaplan, Edgar Ramos, Micha Sharir
In approximate halfspace range counting, one is given a set P of n points in R d, and an ε> 0, and the goal is to preprocess P into a data structure which can answer efficiently queries of the...
Envy-Free Makespan Approximation (2009)
Cohen, Edith, Feldman, Michal, Fiat, Amos, Kaplan, Haim, Olonetsky, Svetlana
We study envy-free mechanisms for scheduling tasks on unrelated machines (agents) that approximately minimize the makespan. For indivisible tasks, we put forward an envy-free poly-time mechanism that...
Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments (2009)
Cohen, Edith, Kaplan, Haim, Sen, Subhabrata
Many data sources are naturally modeled by multiple weight assignments over a set of keys: snapshots of an evolving database at multiple points in time, measurements collected over multiple time...
Kaplan, Haim, Sharir, Micha, Shustin, Eugenii
Let $L$ be a set of $n$ lines in $\reals^d$, for $d\ge 3$. A {\em joint} of $L$ is a point incident to at least $d$ lines of $L$, not all in a common hyperplane. Using a very simple algebraic proof...
On Lines, Joints, and Incidences in Three Dimensions (2009)
Elekes, György, Kaplan, Haim, Sharir, Micha
We extend (and somewhat simplify) the algebraic proof technique of Guth and Katz \cite{GK}, to obtain several sharp bounds on the number of incidences between lines and points in three dimensions....
Maximum Flow in Directed Planar Graphs with Vertex Capacities (2009)
In this paper we present an O(n log n) algorithm for finding a maximum flow in a directed planar graph, where the vertices are subject to capacity constraints, in addition to the arcs. If the source...
Abstract Reach for A ∗: Efficient Point-to-Point Shortest Path Algorithms (2009)
Andrew V. Goldberg, Haim Kaplan, Renato F. Werneck
We study the point-to-point shortest path problem in a setting where preprocessing is allowed. We improve the reach-based approach of Gutman [17] in several ways. In particular, we introduce a...
Leveraging Discarded Samples for Tighter Estimation of Multiple-Set Aggregates (2009)
Many datasets such as market basket data, text or hypertext documents, and sensor observations recorded in different locations or time periods, are modeled as a collection of sets over a ground set...
Abstract. We describe an efficient, purely functional implementation of deques with catenation. In addition to being an intriguing problem in its own right, finding a purely functional implementation...
Strong Price of Anarchy for Machine Load Balancing (2008)
Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky
Abstract. As defined by Aumann in 1959, a strong equilibrium is a Nash equilibrium that is resilient to deviations by coalitions. We give tight bounds on the strong price of anarchy for load...
General General Terms Algorithms (2008)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Räcke’s construction...
1 Introduction The Internet provides a platform for decentralized applications where content or services are requested, stored, and provided by very large number of loosely coupled hosts. In these...
Abstract Reach for A ∗: Efficient Point-to-Point Shortest Path Algorithms (2008)
Andrew V. Goldberg, Haim Kaplan, Renato F. Werneck
We study the point-to-point shortest path problem in a setting where preprocessing is allowed. We improve the reach-based approach of Gutman [17] in several ways. In particular, we introduce a...
Line Transversals of Convex Polyhedra in $\reals^3$ (2008)
Kaplan, Haim, Rubin, Natan, Sharir, Micha
We establish a bound of $O(n^2k^{1+\eps})$, for any $\eps>0$, on the combinatorial complexity of the set $\T$ of line transversals of a collection $\P$ of $k$ convex polyhedra in $\reals^3$ with a...
Haim Kaplan, Tova Milo, Ronen Shabo
comparison of labeling schemes for ancestor queries
We study an extension of the “standard ” learning models to settings where observing the value of an attribute has an associated cost (which might be different for different attributes). Our...
General General Terms Algorithms (2008)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Räcke’s construction...
Variance optimal sampling based estimation of subset sums (2008)
Cohen, Edith, Duffield, Nick, Kaplan, Haim, Lund, Carsten, Thorup, Mikkel
From a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size $k$ that we can later use to estimate the total weight of arbitrary subsets. This is the...
Sketch-Based Estimation of Subpopulation-Weight (2008)
Summaries of massive data sets support approximate query processing over the original data. A basic aggregate over a set of records is the weight of subpopulations specified as a predicate over...
tralizedarchitecturesseemtosupportatmostone:pre partial-matchqueries,butsincesearchisunrelatedtothe vailingprotocols(suchasGnutellaandFastTrack)support...
Abstract Reach for A ∗: Efficient Point-to-Point Shortest Path Algorithms (2008)
Andrew V. Goldberg, Haim Kaplan, Renato F. Werneck
We study the point-to-point shortest path problem in a setting where preprocessing is allowed. We improve the reach-based approach of Gutman [17] in several ways. In particular, we introduce a...
Efficient Sequences of Trials Edith Cohen \Lambda (2008)
An incompetent attorney can delay a trial for months or years. A competent attorney can delay one even longer.
Haim Kaplan, Natan Rubin, Micha Sharir
Abstract. We consider the problem of ray shooting in a three-dimensional scene consisting of k (possibly intersecting) convex polyhedra with a total of n facets. That is, we want to preprocess them...
Strong Price of Anarchy for Machine Load Balancing (2008)
Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky
Abstract. As defined by Aumann in 1959, a strong equilibrium is a Nash equilibrium that is resilient to deviations by coalitions. We give tight bounds on the strong price of anarchy for load...
Finding the position of the k-mismatch and approximate (2008)
Haim Kaplan, Ely Porat, Nira Shafrir
tandem repeats.
Optimal dynamic vertical ray shooting in rectilinear planar subdivisions (2008)
Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. In this paper we consider the dynamic vertical ray shooting problem, that is the task of maintaining a dynamic set S of n non...
Abstract Counting Colors in Boxes ∗ (2008)
Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin
Let P be a set of n points in R d, so that each point is colored by one of C given colors. We present algorithms for preprocessing P into a data structure that efficiently supports queries of the...
ABSTRACT Guarding a Terrain by Two Watchtowers ∗ (2008)
Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Haim Kaplan, Simeon Ntafos, Binhai Zhu
Given a polyhedral terrain T with n vertices, the two-watchtower problem for T calls for finding two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases)...
In a Batched Colored Intersection Searching Problem (CI), (2008)
one is given a set of n geometric objects (of a certain class). Each object is colored by one of c colors, and the goal is to report all pairs of colors (c1, c2) such that there are two objects, one...
Haim Kaplan, Nira Shafrir, Robert E. Tarjan
ÔÖ�� � �Ø � Ø��Ø ��Ø × �Ò �Ø�Ñ Ü �Ò � � ×�Ø � �Ò � �Ò×Û�Ö × ÔÓ×�
Finding Path Minima in Incremental Unrooted Trees ∗ (2008)
Consider a dynamic forest of unrooted trees over a set of n vertices which we update by link operations: Each link operation adds a new edge adjacent to vertices in two different trees. Every edge in...
Processing Top-k Queries from Samples (2008)
Edith Cohen, Nadav Grossaug, Haim Kaplan
Top-k queries are desired aggregation operations on data sets. Examples of queries on network data include finding the top 100 source Autonomous Systems (AS), top 100 ports, or top domain names over...
Line Transversals of Convex Polyhedra in R 3∗ (2008)
Haim Kaplan, Natan Rubin, Micha Sharir
We establish a bound of O(n 2 k 1+ε), for any ε> 0, on the combinatorial complexity of the set T of line transversals of a collection P of k convex polyhedra in R 3 with a total of n facets, and...
1 Restoration by Path Concatenation: Fast Recovery of MPLS Paths (2007)
Anat Bremler-barr, Yehuda Afek, Haim Kaplan, Edith Cohen, Michael Merritt
A new general theory about restoration of network paths is first introduced. The theory pertains to restoration of shortest paths in a network following failure, e.g., we prove that a shortest path...
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi
Abstract. In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage...
Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick
Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs...
Haim Kaplan, Ron Shamir, E. Tarjan
Abstract. We study the parameterizedcomplexity of three NP-hard graph completionproblems. The MINIMUM FILL-IN problem is to decide if a graph can be triangulated by adding at most k edges. We develop...
1 Prefetching the Means for Document Transfer: A New Approach for Reducing Web Latency (2007)
User-perceived latency is recognized as the central performance problem in the Web. We systematically measure factors contributing to this latency, across several locations. Our study reveals that...
and Bar-Ilan University (2007)
Martin Charles Golumbic, Haim Kaplan, Ron Shamir
The Physical Mapping Problem is to reconstruct the relative position of fragments (clones) of DNA along the genome from information on their pairwise overlaps. We show that two simplified versions of...
Martin Charles Golumbic, Haim Kaplan, Ron Shamir, Ron Shamir
The graph sandwich problem for property \Pi is defined as follows: Given two graphs G 1
Connection caching: Model and algorithms (2007)
Edith Cohen, Haim Kaplan, Uri Zwick
We introduce a theoretical model for connection caching. In our model each host maintains (caches) a limited number of open connections to other hosts. A request may utilize an open connection in...
Haim Kaplan, Ron Shamir, E. Tarjan
Abstract. We give a quadratic-time algorithm for nding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and...
Haim Kaplan, Nira Shafrir, Robert E. Tarjan
In the classical union-find problem we maintain a partition of a universe of n elements into disjoint sets subject to the operations union and find. The operation union(A; B;C) replaces sets A and B...
We present a randomized procedure for rounding fractional perfect matchings to (integral) matchings. If the original fractional matching satises any linear inequality, then with high probability, the...
Harold N. Gabow, Robert E. Tarjan, Haim Kaplan, Haim Kaplan
We consider the problem of testing the uniqueness of maximum matchings, both in the unweighted and in the weighted case. For the unweighted case, we have two results. First, given a graph with n...
Meldable Heaps and Boolean Union-Find (extended abstract) (2007)
Haim Kaplan, Nira Shafrir, Robert E. Tarjan
In the classical meldable heap data type we maintain an item-disjoint collection of heaps under the operations ndmin, insert, delete, decrease-key, and meld. In the usual de nition decrease-key and...
Abstract Reachability and distance queries via 2-hop labels (2007)
Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick
Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs...
Reality is merely an illusion, albeit a very persistent one. (2007)
We address a longstanding open problem of [10, 9], and present a general transformation that transforms any pointer based data structure to be con uently persistent. Such transformations for fully...
The success of a P2P file-sharing network highly depends on the scalability and versatility of its search mechanism. Two particularly desirable search features are scope (ability to find infrequent...
Abstract. The problem of sorting signed permutations by reversals (SBR) is a fundamental problem in computational molecular biology. The goal is, given two genomes (represented as permutations of the...
Web www.it-c.dk Identifying Nearest Common Ancestors in a Distributed Environment (2007)
Cyril Gavoille, Cyril Gavoille, Haim Kaplan, Haim Kaplan, Theis Rauhe, Theis Rauhe, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. ISSN 1600-6100 ISBN 87-7949-008-5
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi
Abstract. In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage...
Edith Cohen, Eran Halperin, Haim Kaplan
Performance aspects of distributed caches using
1 Refreshment Policies for Web Content Caches (2007)
Web content caches are often placed between end-users and origin servers as a mean to reduce server load, network usage, and ultimately, user-perceived latency. Cached objects typically have...
Edith Cohen, Haim Kaplan, Uri Zwick
Abstract. We present a competitive analysis of the LRFU paging algorithm, a hybrid of the LRU (Least Recently Used) and LFU (Least Frequently Used) paging algorithms. We show that the competitive...
Data Structures for Mergeable Trees (2007)
Georgiadis, Loukas, Kaplan, Haim, Shafrir, Nira, Tarjan, Robert E., Werneck, Renato F.
Motivated by an application in computational topology, we consider a novel variant of the problem of efficiently maintaining dynamic rooted trees. This variant requires merging two paths in a single...
Seminar on Advanced topics in data structures Spring 2006/2007 (2007)
We shall focus on algorithms for combinatorial optimization problems. Specifically, we will study the maximum flow problem, the minimum cost flow problem, maximum matchings, and minimum cuts, and...
Weak ɛ-nets and interval chains (2007)
Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky
We construct weak ɛ-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1 r-nets of size O(rα(r)), where α(r)...
Counting colors in boxes (2007)
Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin
Let P be a set of n points in R d, so that each point is colored by one of C given colors. We present algorithms for preprocessing P into a data structure that efficiently supports queries of the...
Computing the volume of the union of cubes (2007)
Pankaj K. Agarwal, Haim Kaplan, Micha Sharir
Let C be a set of n axis-aligned cubes in R 3, and let U(C) denote the union of C. We present an algorithm that can compute the volume of U(C) in time O(n 4/3 log n). The previously best known...
Counting colors in boxes (2007)
Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin
Let P be a set of n points in R d, so that each point is colored by one of C given colors. We present algorithms for preprocessing P into a data structure that efficiently supports queries of the...
Kinetic and Dynamic Data Structures for Closest Pairs and All Nearest Neighbors ∗ (2007)
Pankaj K. Agarwal, Haim Kaplan, Micha Sharir
We present simple fully dynamic and kinetic data structures, which are variants of a dynamic 2-dimensional range tree, for maintaining the closest pair and all nearest neighbors for a set of n moving...
Kinetic and Dynamic Data Structures for Closest Pairs and All Nearest Neighbors ∗ (2007)
Pankaj K. Agarwal, Haim Kaplan, Micha Sharir
We present simple fully dynamic and kinetic data structures, which are variants of a dynamic 2-dimensional range tree, for maintaining the closest pair and all nearest neighbors for a set of n moving...
Strong Price of Anarchy for Machine Load Balancing (2007)
Fiat, Amos, Levy, Meital, Kaplan, Haim, Olonetsky, Svetlana
As defined by Aumann in 1959, a strong equilibrium is a Nash equilibrium that is resilient to deviations by coalitions. We give tight bounds on the strong price of anarchy for load balancing on...
Weak ɛ-nets and interval chains (2007)
Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky
We construct weak ɛ-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1 r-nets of size O(rα(r)), where α(r)...
A simpler analysis of Burrows-Wheeler based compression (2006)
Haim Kaplan, Shir Landau, Elad Verbin
In this paper we present a new technique for worst-case analysis of compression algorithms which are based on the Burrows-Wheeler Transform. We deal mainly with the algorithm proposed by Burrows and...
R.F.: Better landmarks within reach (2006)
Andrew V. Goldberg, Haim Kaplan, Renato F. Werneck
Abstract. We present significant improvements to a practical algorithm for the point-to-point shortest path problem on road networks that combines A ∗ search, landmark-based lower bounds, and...
Reach for A ∗ : Efficient point-to-point shortest path algorithms (2006)
Andrew V. Goldberg, Haim Kaplan, Renato F. Werneck
We study the point-to-point shortest path problem in a setting where preprocessing is allowed. We improve the reach-based approach of Gutman [16] in several ways. In particular, we introduce a...
On the price of stability for designing undirected networks with fair cost allocations (2006)
Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky
Abstract. In this paper we address the open problem of bounding the price of stability for network design with fair cost allocation for undirected graphs posed in [1]. We consider the case where...
A simpler analysis of Burrows-Wheeler based compression (2006)
Haim Kaplan, Shir Landau, Elad Verbin
In this paper we present a new technique for worst-case analysis of compression algorithms which are based on the Burrows-Wheeler Transform. We deal mainly with the algorithm purposed by Burrows and...
Elad Verbin, Curriculum Vitæ, Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin, ...
received best paper award in Combinatorial Pattern Matching (CPM) 2006. To be published in Theoretical Computer Science, special issue on The Burrows-Wheeler Transform and its Applications (expected...
A simpler linear-time recognition of circular-arc graphs (2006)
Abstract. We give a linear time recognition algorithm for circular-arc graphs. Our algorithm is much simpler than the linear time recognition algorithm of McConnell [10] (which is the only linear...
Online conflict-free coloring for intervals (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel
Abstract. We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the...
Abstract We present new algorithms for approximate range counting,where, for a specified "> 0, we want to count the number of data points in a query range, up to relative error...
R.F.: Better landmarks within reach (2006)
Andrew V. Goldberg, Haim Kaplan, Renato F. Werneck
Abstract. We present significant improvements to a practical algorithm for the point-to-point shortest path problem on road networks that combines A ∗ search, landmark-based lower bounds, and...
Certifying algorithms for recognizing proper circulararc graphs and unit circular-arc graphs (2006)
Abstract. We give two new algorithms for recognizing proper circulararc graphs and unit circular-arc graphs. The algorithms either provide a model for the input graph, or a certificate that proves...
We present new algorithms for approximate range counting, where, for a specified ε> 0, we want to count the number of data points in a query range, up to relative error of ε. We first describe a...
Online Conflict-Free Coloring for Intervals 1 (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Online Conflict-Free Coloring for Intervals 1 (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
R.F.: Better landmarks within reach (2006)
Andrew V. Goldberg, Haim Kaplan, Renato F. Werneck
Abstract. We present significant improvements to a practical algorithm for the point-to-point shortest path problem on road networks that combines A ∗ search, landmark-based lower bounds, and...
Online conflict-free coloring for intervals (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Ji Rí, Matou Sek, ...
Abstract. We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the...
R.F.: Better landmarks within reach (2006)
Andrew V. Goldberg, Haim Kaplan, Renato F. Werneck
We study the real algorithm for the point-to-point shortest path problem. It combines A ∗ search search, landmark-based lower bounds, and reach-based pruning. We suggest several improvements to the...
On the price of stability for designing undirected networks with fair cost allocations (2006)
Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky, Ronen Shabo
Abstract. In this paper we address the open problem of bounding the price of stability for network design with fair cost allocation for undirected graphs posed in [1]. For the version of this problem...
Thin Heaps, Thick Heaps (2006)
The Fibonacci heap was devised to provide an especially efficient implementation of Dijkstra’s shortest path algorithm. Although asyptotically efficient, it is not as fast in practice as other heap...
Learning with Attribute Costs (2005)
Kaplan, Haim, Kushilevitz, Eyal, Mansour, Yishay
We study an extension of the ``standard'' learning models to settings where observing the value of an attribute has an associated cost (which might be different for different attributes). Our model...
Guarding a terrain by two watchtowers (2005)
Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Haim Kaplan, Simeon Ntafos, Micha Sharir, ...
Given a polyhedral terrain T with n vertices, the two-watchtower problem for T asks to find two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie on...
Online Conflict-Free Coloring for Intervals 1 (2004)
Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, Micha Sharir, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Online Conflict-Free Coloring for Intervals 1 (2004)
Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, Micha Sharir, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Sorting Signed Permutations by Reversals, Revisited \Lambda (2004)
Abstract The problem of sorting signed permutations by reversals (SBR) is a fundamental problem in computational molecular biology. The goal is, given a signed permutation, to find a shortest...
Optimal oblivious routing in polynomial time (2003)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any undirected network there is an oblivious routing algorithm with a polylogarithmic competitive ratio with respect to congestion. Unfortunately,...
Efficient Sequences of Trials (2003)
Edith Cohen, Amos Fiat, Haim Kaplan, Evelle J. Younger, La Times
We introduce a problem called sequential trial optimization, a generalization of the well studied set cover problem with a new objective function. We give a simple algorithm that achieves a constant...
Addendum to "Scalable Secure Storage when Half the System is (2003)
Faulty Noga Alon, Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern
Introduction. We consider the following problem. A file of size s bits is to be stored on n disks. Our failure model assumes that a potentially malicious adversary may choose after the file is stored...
Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs (2003)
Haim Kaplan, Nira Shafrir, Moshe Lewenstein, Maxim Sviridenko
A directed multigraph is said to be d-regular if the indegree and outdegree of every vertex is exactly d. By Hall’s theorem one can represent such a multigraph as a combination of at most n 2 cycle...
Optimal Oblivious Routing in Polynomial Time (2003)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Räcke's...
Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs (2002)
Buchsbaum, Adam L., Georgiadis, Loukas, Kaplan, Haim, Rogers, Anne, Tarjan, Robert E., Westbrook, Jeffery R.
We present algorithms that run in linear time on pointer machines for a collection of problems, each of which either directly or indirectly requires the evaluation of a function defined on paths in a...
Nearest common ancestors: A survey and a new distributed algorithm (2002)
Stephen Alstrup, Cyril Gavoille, Haim Kaplan, Theis Rauhe
Several papers describe linear time algorithms to preprocess a tree, such that one can answer subsequent nearest common ancestor queries in constant time. Here, we survey these algorithms and related...
Reachability and Distance Queries via 2-hop Labels (2002)
Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick
1 Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs...
Nearest common ancestors: A survey and a new distributed algorithm (2002)
Stephen Alstrup, Cyril Gavoille, Haim Kaplan, Theis Rauhe
Several papers describe linear time algorithms to preprocess a tree, such that one can answer subsequent nearest common ancestor queries in constant time. Here, we survey these algorithms and related...
Predicting and bypassing end-to-end Internet service degradations (2002)
Anat Bremler-barr, Edith Cohen, Haim Kaplan, Yishay Mansour
We study the patterns and predictability of Internet End-to-End service degradations, where a degradation is a significant deviation of the round trip time between a client and a server. We use...
Labeling Dynamic XML Trees (2002)
Edith Cohen Att, Edith Cohen, Haim Kaplan, Tova Milo
We present algorithms to label the nodes of an XML tree which is subject to insertions and deletions of nodes. The labeling is done such that (1) we label each node immediately when it is inserted...
Balanced-replication algorithms for distribution trees (2002)
Abstract In many Internet applications, requests for a certain object are routed bottom-up over a tree where the root of the tree is the node containing the object. When an object becomes popular,...
Faster kinetic heaps and their use in broadcast scheduling (2001)
Haim Kaplan, Robert E. Tarjan, Kostas Tsioutsiouliklis
We describe several implementations of the kinetic heap, a heap (priority queue) in which the key of each item, instead of being xed, is a linear function of time. The kinetic heap is a simple...
Refreshment policies for web content caches (2001)
Web content caches are often placed between end-users and origin servers as a mean to reduce server load, network usage, and ultimately, user-perceived latency. Cached objects typically have...
Competitive analysis of the LRFU paging algorithm (2001)
Edith Cohen, Haim Kaplan, Uri Zwick
We present a competitive analysis of the LRFU paging algorithm, a hybrid of the LRU (Least Recently Used) and LFU (Least Frequently Used) paging algorithms. We show that the competitive ratio of LRFU...
Seminar on Advanvced Topics in Data Structures (2001)
We shall focus on the following topics in data structures
Restoration by Path Concatenation: Fast Recovery of MPLS Paths (2001)
Yehuda Afek, Anat Bremler-barr, Haim Kaplan, Edith Cohen, Michael Merritt
A new general theory about restoration of network paths is rst introduced. The theory pertains to restoration of shortest paths in a network following failure, e.g., we prove that a shortest path in...
Aging through cascaded caches: Performance issues in the distribution of web content (2001)
The Web is a distributed system, where data is stored and disseminated from both origin servers and caches. Origin servers provide the most up-to-date copy whereas caches store and serve copies that...
Compact labeling schemes for ancestor queries (2001)
Haim Kaplan, Tova Milo, Ronen Shabo
Motivated by a recent application in XML search engines we study the problem of labeling the nodes of a tree (XML file) such that given the labels of two nodes one can determine whether one node is...
Short and simple labels for small distances and other functions (2001)
Haim Kaplan, Tova Milo, Log N, For D O
Abstract. We present a labeling scheme for rooted trees which allows to compute, from the label of v alone, unique identiers for the ancestors of v that are at distance at most d from v. For any...
Compact labeling schemes for ancestor queries (2001)
Serge Abiteboul, Haim Kaplan, Tova Milo
We consider the following problem. Give a rooted tree T, label the nodes of T in the most compact way such that given the labels of two nodes one can determine in constant time, by looking only at...
Faster kinetic heaps and their use in broadcast scheduling (2001)
Haim Kaplan, Robert E. Tarjan, Kostas Tsioutsiouliklis
We describe several implementations of the kinetic heap, a heap (priority queue) in which the key of each item, instead of being fixed, is a linear function of time. The kinetic heap is a simple...
Restoration by Path Concatenation: Fast Recovery of MPLS Paths (2001)
Anat Bremler-barr, Yehuda Afek, Haim Kaplan, Edith Cohen, Michael Merritt
A new general theory about restoration of network paths is rst introduced. The theory pertains to restoration of shortest paths in a network following failure, e.g., we prove that a shortest path in...
Faster kinetic heaps and their use in broadcast scheduling (2001)
Haim Kaplan, Robert E. Tarjan, Kostas Tsioutsiouliklis
3 We describe several implementations of the kinetic heap, a heap (priority queue) in which the key of each item, instead of being xed, is a linear function of time. The kinetic heap is a simple...
Proactive caching of DNS records: Addressing a performance bottleneck (2001)
The resolution of a host name to an IP-address is a necessary predecessor to connection establishment and HTTP exchanges. Nonetheless, DNS resolutions often involve multiple remote name-servers and...
The age penalty and its effect on cache performance (2001)
Web content caching is recognized as an effective mechanism to decrease server load, network traffic, and user-perceived latency. An HTTP compliant cache associates with each cached object an...
Compact labeling schemes for ancestor queries (2001)
Serge Abiteboul, Haim Kaplan, Tova Milo
We consider the following problem. Give a rooted tree T, label the nodes of T in the most compact way such that given the labels of two nodes one can determine in constant time, by looking only at...
Competitive analysis of the LRFU paging algorithm (2001)
Edith Cohen Haim, Edith Cohen, Haim Kaplan, Uri Zwick
We present a competitive analysis of the LRFU paging algorithm, a hybrid of the LRU (Least Recently Used) and LFU (Least Frequently Used) paging algorithms. We show that the competitive ratio of LRFU...
Restoration by Path Concatenation: Fast Recovery of MPLS Paths (2001)
Yehuda Afek, Anat Bremler-barr, Haim Kaplan, Edith Cohen, Michael Merritt
A new general theory about restoration of network paths is first introduced. The theory pertains to restoration of shortest paths in a network following failure, e.g., we prove that a shortest path...
A Comparison of Labeling Schemes for Ancestor Queries (2001)
Haim Kaplan, Tova Milo, Ronen Shabo
XML documents are often viewed as trees (basically the parse tree of the document), and queries over such documents typically test for ancestor relationships among tree nodes. Search engines process...
Short and Simple Labels for Small Distances and Other Functions (2001)
Haim Kaplan, Tova Milo, Log N, For D O
We present a labeling scheme for rooted trees which allows to compute, from the label of v alone, unique identi ers for the ancestors of v that are at distance at most d from v. For any constant d...
Making Data Structures Confluently Persistent (2001)
Reality is merely an illusion, albeit a very persistent one.
Compact Labeling Schemes for Ancestor Queries (2001)
Exte Nd Ed, Serge Abiteboul, Haim Kaplan, Tova Milo
Serge Abiteboul Haim Kaplan Tova Milo Abstract We consider the following problem. Give a rooted tree T , label the nodes of T in the most compact way such that given the labels of two nodes one can...
Scalable Secure Storage when Half the System Is Faulty (2000)
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern
In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...
Scalable Secure Storage when Half the System Is Faulty (2000)
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern
In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...
Scalable Secure Storage when Half the System Is Faulty (2000)
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern
In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...
Scalable Secure Storage when Half the System Is Faulty (2000)
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern
In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...
Connection Caching under (2000)
Various Models Of, Edith Cohen, Haim Kaplan, Uri Zwick
Motivated by Web applications, we recently introduced the following theoretical model for connection-caching: Each host on a network can maintain (cache) a limited number of connections to other...
Prefetching the Means for Document Transfer: A New Approach for Reducing Web Latency (2000)
User-perceived latency is recognized as the central performance problem in the Web. We systematically measure factors contributing to this latency, across several locations. Our study reveals that...
Prefetching the Means for Document Transfer: A New Approach for Reducing Web Latency (2000)
User-perceived latency is recognized as the central performance problem in the Web. We systematically measure factors contributing to this latency, across several locations. Our study reveals that...
Caching documents with variable sizes and fetching costs: an LP based approach (1999)
We give an integer programming formulation of the paging problem with varying sizes and fetching costs. We use this formulation to provide an alternative proof that a variant of the algorithm...
On-line complexity of Monotone Set Systems (1999)
On-line analysis models a player A (randomized or deterministic) who makes immediate responses to incoming elements of an input sequence s = a 1: : : a r. In this paper a 1; : : : ; a r are...
Exploiting regularities in Web traffic patterns for cache replacement (1999)
Caching web pages at proxies and in web servers' memories can greatly enhance performance. Proxy caching is known to reduce network load and both proxy and server caching can significantly...
Purely functional, real-time deques with catenation (1999)
We describe an efficient, purely functional implementation of deques with catenation. In addition to being an intriguing problem in its own right, finding a purely functional implementation of...
Bounded degree interval sandwich problems (1999)
The problems of Interval Sandwich (IS) and Intervalizing Colored Graphs (ICG) have received a lot of attention recently, due to their applicability to DNA physical mapping problems with ambiguous...
Policies for managing TCP connections under persistent HTTP (1999)
Edith Cohen, Haim Kaplan, Jeffrey D. Oldham
Hyper Text Transfer Protocol (HTTP) traffic dominates Internet traffic. The exchange of HTTP messages is implemented using the connection-oriented TCP. HTTP/1.0 establishes a new TCP connection for...
Exploiting regularities in Web traffic patterns for cache replacement (1999)
Abstract Caching web pages at proxies and in web servers ' memories can greatly enhance performance. Proxy caching is known to reduce network load and both proxy and server caching can...
Exploiting regularities in Web traffic patterns for cache replacement (1999)
Caching web pages at proxies and in web servers ' memories can greatly enhance performance. Proxy caching is known to reduce network load and both proxy and server caching can significantly...
Edith Cohen, Haim Kaplan, Uri Zwick
Communication between clients and servers in the Web is performed using TCP (Transmission Control Protocol). TCP first opens a connection between the two nodes and then sends data packets via this...
Caching Documents with Variable Sizes and Fetching Costs: An LP-Based Approach (1999)
We give an integer programming formulation of the paging problem with varying sizes and fetching costs. We use this formulation to provide an alternative proof that a variant of the algorithm...
Just the Fax-Differentiating Voice and Fax Phone Lines Using Call Billing Data (1999)
Haim Kaplan, Martin Strauss, Mario Szegedy
this paper we are particularly concerned with classifying lines as either voice or fax, we point out that the techniques we use may apply in other classification problems as well. The ability to...
Bounded Degree Interval Sandwich Problems (1999)
The problems of Interval Sandwich (IS) and Intervalizing Colored Graphs (ICG) have received a lot of attention recently, due to their applicability to DNA physical mapping problems with ambiguous...
A New, Simpler Linear-Time Dominators Algorithm (1999)
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
this article is organized as follows. Section 2 outlines Lengauer and Tarjan's approach. Section 3 gives a broad overview of our algorithm and differentiates it from previous work. Section 4...
On-line Complexity of Monotone Set Systems (1999)
On-line analysis models a player A (randomized or deterministic) who makes immediate responses to incoming elements of an input sequence s = a1 : : : ar . In this paper a1 ; : : : ; ar are...
Edith Cohen Haim, Edith Cohen, Haim Kaplan, Uri Zwick
Communication between clients and servers in the Web is performed using TCP (Transmission Control Protocol) . TCP first opens a connection between the two nodes and then sends data packets via this...
Managing TCP Connections under Persistent HTTP (1999)
Edith Cohen, Haim Kaplan, Jeffrey D. Oldham
Hyper Text Transfer Protocol (HTTP) traffic dominates Internet traffic. The exchange of HTTP messages is implemented using the connection-oriented TCP.
Simple confluently persistent catenable lists (1998)
Haim Kaplan, Chris Okasaki, E. Tarjan
Abstract. We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive {...
A new, simpler linear-time dominators algorithm (1998)
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
We present a new linear-time algorithm to nd the immediate dominators of all vertices in a owgraph. Our algorithm is simpler than previous linear-time algorithms: rather than employ complicated data...
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
We present two new data structure tools---disjoint set union with bottom-up linking, and pointer-based radix sort---and combine them with bottom-level microtrees to devise the first linear-time...
Simple confluently persistent catenable lists (1998)
Haim Kaplan, Chris Okasaki, Robert E. Tarjan
Abstract. We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive-each...
A New, Simpler Linear-Time Dominators Algorithm (1998)
Adam Buchsbaum Haim, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
We present a new linear-time algorithm to find the immediate dominators of all vertices in a flowgraph. Our algorithm is simpler than previous linear-time algorithms: we combine the use of microtrees...
Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals (1998)
Haim Kaplan, Ron Shamir, Robert E. Tarjan
We give a quadratic algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its...
Simple Confluently Persistent Catenable Lists (Extended Abstract) (1998)
Haim Kaplan, Chris Okasaki, Robert E. Tarjan
We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive -- each...
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
We present two new data structure tools---disjoint set union with bottom-up linking, and pointer-based radix sort---and combine them with bottom-level microtrees to devise the first linear-time...
On-line Complexity of Monotone Set Systems (1998)
On-line models assume a player, A (randomized or deterministic), who makes immediate responses to incomming elements of an input sequence s = a 1 : : : a r . In this paper we study the case, when the...
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
We present two new data structure tools—disjoint set union with bottom-up linking, and pointer-based radix sort—and combine them with bottom-level microtrees to devise the first linear-time...
Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals (1997)
Haim Kaplan, Ron Shamir, Robert E. Tarjan
We give a quadratic algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its...
A Faster Primal Network Simplex Algorithm (1996)
Aggarwal, Charu C., Kaplan, Haim
We present a faster implementation of the polynomial time primal simplex algorithm due to Orlin [23]. His algorithm requires O(nm min{log(nC), m log n}) pivots and O(n2 m ??n{log nC, m log n}) time....
A Faster Primal Network Simplex Algorithm (1996)
Aggarwal, Charu C., Kaplan, Haim
We present a faster implementation of the polynomial time primal simplex algorithm due to Orlin [23]. His algorithm requires O(nm min{log(nC), m log n}) pivots and O(n2 m ??n{log nC, m log n}) time....
Purely functional representations of catenable sorted lists (1996)
The power of purely functional programming in the construction of data structures has received much attention, not only because functional languages have many desirable properties, but because...
Pathwidth, bandwidth and completion problems to proper interval graphs with small cliques (1996)
We study two related problems motivated by molecular biology: ffl Given a graph G and a constant k, does there exist a supergraph G 0 of G which is a unit interval graph and has clique size at most...
TR-511-96 Purely Functional Representations of Catenable Sorted Lists. (1996)
The power of purely functional programming in the construction of data structures has received much attention, not only because functional languages have many desirable properties, but because...
Physical Maps and Interval Sandwich Problems: Bounded Degrees Help (1996)
The problems of Interval Sandwich (IS) and Intervalizing Colored Graphs (ICG) have received a lot of attention recently, due to their applicability to DNA physical mapping problems with ambiguous...
We present approximation schemes for "dense" instances of many well-known NP-hard problems, including 0-1 quadratic-assignment, (an optimization formulation of) graphisomorphism,...
Purely Functional Representations of Catenable Sorted Lists. (1996)
The power of purely functional programming in the construction of data structures has received much attention, not only because functional languages have many desirable properties, but because...
Sanjeev Arora, Alan Frieze, Haim Kaplan
We present approximation schemes for "dense" instances of many well-known NP-hard problems, including 0-1 quadratic-assignment, (an optimization formulation of) graphisomorphism,...
Sanjeev Arora, Alan Frieze, Haim Kaplan
We present a randomized procedure for rounding fractional perfect matchings to (integral) matchings. If the original fractional matching satisfies any linear inequality, then with high probability,...
Four strikes against physical mapping of DNA (1995)
Paul W. Goldberg, Martin C. Golumbic, Haim Kaplan, Ron Shamir
Physical Mapping is a central problem in molecular biology and the human genome project. The problem is to reconstruct the relative position of fragments of DNA along the genome from information on...
Four Strikes Against Physical Mapping of DNA (1995)
Paul W. Goldberg, Martin C. Golumbic, Haim Kaplan, Ron Shamir
Physical Mapping is a central problem in molecular biology and the human genome project. The problem is to reconstruct the relative position of fragments of DNA along the genome from information on...
Persistent data structures Haim Kaplan (1995)
this paper is as follows. Section 1.2 describes few algorithms that use persistent data structures to achieve their best time or space bounds. Section 1.3 surveys the general methods to make data...
The domatic number problem on some perfect graph families (1994)
An extremely simple, linear time algorithm is given for constructing a domatic partition in totally balanced hypergraphs. This simplifies and generalizes previous algorithms for interval and strongly...
Pathwidth, Bandwidth and Completion Problems to Proper Interval Graphs with Small Cliques (1994)
We study two related problems motivated by molecular biology: ffl Given a graph G and a constant k, does there exist a supergraph G 0 of G which is a unit interval graph and has clique size at most...
Haim Kaplan, Ron Shamir, Robert E. 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...
Algorithms and Complexity of Sandwich Problems in Graphs (extended ) (1994)
Martin Charles Golumbic, Haim Kaplan, Ron Shamir, Ramat Gan Israel
.Given two graphs G 1 = (V, E 1 ) and G = (V, E 2 ) such that E 1 ` E 2 , is there a graph G = (V, E) such that E 1 ` E ` E 2 which belongs to a specified graph family? Such problems generalize...