Publications (59)
Union of Random Minkowski Sums and Network Vulnerability Analysis
Pankaj Agarwal, Sariel Har-Peled, Haim Kaplan +1
Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions
Pankaj K. Agarwal, Haim Kaplan, Natan Rubin +1
Maximum Flow in Directed Planar Graphs with Vertex Capacities
Haim Kaplan, Yahav Nussbaum
Selection from heaps, row-sorted matrices and $X+Y$ using soft heaps
Haim Kaplan, László Kozma, Or Zamir +1
Pairing heaps: the forward variant
Dani Dorfman, Haim Kaplan, László Kozma +1
Minimal Indices for Successor Search
Sarel Cohen, Amos Fiat, Moshik Hershcovitch +1
Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments
Edith Cohen, Haim Kaplan, Subhabrata Sen
Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
Esther Ezra, Sariel Har-Peled, Haim Kaplan +1
General techniques for approximate incidences and their application to the camera posing problem
Dror Aiger, Haim Kaplan, Efi Kokiopoulou +2
Stable Delaunay Graphs
Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas +3
Computing the Discrete Fréchet Distance in Subquadratic Time
Pankaj K. Agarwal, Rinat Ben Avraham, Haim Kaplan +1
Competitive Analysis with a Sample and the Secretary Problem
Haim Kaplan, David Naori, Danny Raz
Min-Cost Flow Duality in Planar Networks
Haim Kaplan, Yahav Nussbaum
Truth and Envy in Capacitated Allocation Games
Edith Cohen, Michal Feldman, Amos Fiat +2
Improved bounds for multipass pairing heaps and path-balanced binary search trees
Dani Dorfman, Haim Kaplan, László Kozma +2
Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information
Edith Cohen, Haim Kaplan
Approximating the $k$-Level in Three-Dimensional Plane Arrangements
Sariel Har-Peled, Haim Kaplan, Micha Sharir
Approximate Minimum-Weight Matching with Outliers under Translation
Pankaj K. Agarwal, Haim Kaplan, Geva Kipper +4
Clustering Small Samples with Quality Guarantees: Adaptivity with One2all pps
Edith Cohen, Shiri Chechik, Haim Kaplan
Line Transversals of Convex Polyhedra in $\reals^3$
Haim Kaplan, Natan Rubin, Micha Sharir
The Temp Secretary Problem
Amos Fiat, Ilia Gorelik, Haim Kaplan +1
Envy-Free Makespan Approximation
Edith Cohen, Michal Feldman, Amos Fiat +2
Triangles and Girth in Disk Graphs and Transmission Graphs
Haim Kaplan, Katharina Klost, Wolfgang Mulzer +3
Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs
Adam L. Buchsbaum, Loukas Georgiadis, Haim Kaplan +3
Prophet Secretary: Surpassing the $1-1/e$ Barrier
Yossi Azar, Ashish Chiplunkar, Haim Kaplan
On the Complexity of Hub Labeling
Maxim Babenko, Andrew V. Goldberg, Haim Kaplan +2
Stream sampling for variance-optimal estimation of subset sums
Edith Cohen, Nick Duffield, Haim Kaplan +2
Adjacency labeling schemes and induced-universal graphs
Stephen Alstrup, Haim Kaplan, Mikkel Thorup +1
Hierarchical Reinforcement Learning: Approximating Optimal Discounted TSP Using Local Policies
Tom Zahavy, Avinatan Hasidim, Haim Kaplan +1
Improved Bounds for Geometric Permutations
Natan Rubin, Haim Kaplan, Micha Sharir
A Kinetic Triangulation Scheme for Moving Points in The Plane
Haim Kaplan, Natan Rubin, Micha Sharir
On the Interplay between Incentive Compatibility and Envy Freeness
Edith Cohen, Michal Feldman, Amos Fiat +2
Leveraging Discarded Samples for Tighter Estimation of Multiple-Set Aggregates
Edith Cohen, Haim Kaplan
Sketch-Based Estimation of Subpopulation-Weight
Edith Cohen, Haim Kaplan
A faster algorithm for the discrete Fréchet distance under translation
Rinat Ben Avraham, Haim Kaplan, Micha Sharir
Hollow Heaps
Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan +1
Polylogarithmic Bounds on the Competitiveness of Min-cost (Bipartite) Perfect Matching with Delays
Yossi Azar, Ashish Chiplunkar, Haim Kaplan
Data Structures for Mergeable Trees
Loukas Georgiadis, Haim Kaplan, Nira Shafrir +2
What you can do with Coordinated Samples
Edith Cohen, Haim Kaplan
Differentially Private Learning of Geometric Concepts
Haim Kaplan, Yishay Mansour, Yossi Matias +1
On Lines, Joints, and Incidences in Three Dimensions
György Elekes, Haim Kaplan, Micha Sharir
Fibonacci Heaps Revisited
Haim Kaplan, Robert E. Tarjan, Uri Zwick
Routing in Unit Disk Graphs
Haim Kaplan, Wolfgang Mulzer, Liam Roditty +1
On lines and Joints
Haim Kaplan, Micha Sharir, Eugenii Shustin
Joint Cache Partition and Job Assignment on Multi-Core Processors
Avinatan Hassidim, Haim Kaplan, Omry Tuval
Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees
Shiri Chechik, Edith Cohen, Haim Kaplan
Unit Distances in Three Dimensions
Haim Kaplan, Jiri Matousek, Zuzana Safernova +1
Learning to Screen
Alon Cohen, Avinatan Hassidim, Haim Kaplan +2
Probe Scheduling for Efficient Detection of Silent Failures
Edith Cohen, Avinatan Hassidim, Haim Kaplan +3
Kinetic Stable Delaunay Graphs
Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas +4
A Labeling Approach to Incremental Cycle Detection
Edith Cohen, Amos Fiat, Haim Kaplan +1
The AND-OR game: Equilibrium Characterization (Working Paper)
Avinatan Hassidim, Haim Kaplan, Yishay Mansour +1
Simple Proofs of Classical Theorems in Discrete Geometry via the Guth--Katz Polynomial Partitioning Technique
Haim Kaplan, JiÅà MatouÅ¡ek, Micha Sharir
Non-Price Equilibria in Markets of Discrete Goods
Avinatan Hassidim, Haim Kaplan, Yishay Mansour +1
Finding the Maximal Empty Rectangle Containing a Query Point
Haim Kaplan, Micha Sharir
Representations of Sparse Distributed Networks: A Locality-Sensitive Approach
Haim Kaplan, Shay Solomon
Differentially Private k-Means with Constant Multiplicative Error
Haim Kaplan, Uri Stemmer
The Discrete and Semi-continuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection Techniques
Rinat Ben Avraham, Omrit Filtser, Haim Kaplan +2
Epsilon-Nets for Halfspaces Revisited
Sariel Har-Peled, Haim Kaplan, Micha Sharir +1