Home

Haim Kaplan

  1. How to Estimate Change from Samples.

    Fri, 03/23/2012 - 15:01 — SomNambul
    Authors: Edith Cohen, Haim Kaplan
    Subjects: Data Structures and Algorithms
    Abstract

    Measurement data, snapshots of a system, and traffic or activity logs are
    typically collected repeatedly. {\em Difference queries}, which identify and
    measure change, are central to anomaly detection, monitoring, and planning.
    When the data is sampled, as is often necessary to meet resource constraints,
    queries need to be processed over the sampled data. Surprisingly, however, we
    are not aware of pre-existing satisfactory estimators even for Euclidean
    distances.

  2. Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information.

    Thu, 09/08/2011 - 15:01 — SomNambul
    Authors: Edith Cohen, Haim Kaplan
    Subjects: Databases
    Abstract

    Random sampling is an essential tool in the processing and transmission of
    data. It is used to summarize data too large to store or manipulate and meet
    resource constraints on bandwidth or battery power. Estimators that are applied
    to the sample facilitate fast approximate processing of queries posed over the
    original data and the value of the sample hinges on the quality of these
    estimators.

  3. Simple Proofs of Classical Theorems in Discrete Geometry via the Guth--Katz Polynomial Partitioning Technique.

    Tue, 03/01/2011 - 16:01 — SomNambul
    Authors: Micha Sharir, Haim Kaplan, Jiří Matoušek
    Subjects: Combinatorics
    Abstract

    Recently Guth and Katz \cite{GK2} invented, as a step in their nearly
    complete solution of Erd\H{o}s's distinct distances problem, a new method for
    partitioning finite point sets in $\R^d$, based on the Stone--Tukey polynomial
    ham-sandwich theorem. We apply this method to obtain new and simple proofs of
    two well known results: the Szemer\'edi--Trotter theorem on incidences of
    points and lines, and the existence of spanning trees with low crossing
    numbers. Since we consider these proofs particularly suitable for teaching, we
    aim at self-contained, expository treatment.

  4. A Kinetic Triangulation Scheme for Moving Points in The Plane.

    Fri, 05/07/2010 - 15:02 — SomNambul
    Authors: Micha Sharir, Haim Kaplan, Natan Rubin
    Subjects: Computational Geometry
    Abstract

    We present a simple randomized scheme for triangulating a set $P$ of $n$
    points in the plane, and construct a kinetic data structure which maintains the
    triangulation as the points of $P$ move continuously along piecewise algebraic
    trajectories of constant description complexity. Our triangulation scheme
    experiences an expected number of $O(n^2\beta_{s+2}(n)\log^2n)$ discrete
    changes, and handles them in a manner that satisfies all the standard
    requirements from a kinetic data structure: compactness, efficiency, locality
    and responsiveness.

  5. On the Interplay between Incentive Compatibility and Envy Freeness.

    Tue, 03/30/2010 - 15:02 — SomNambul
    Authors: Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky
    Subjects: Computer Science and Game Theory
    Abstract

    We study mechanisms for an allocation of goods among agents, where agents
    have no incentive to lie about their true values (incentive compatible) and for
    which no agent will seek to exchange outcomes with another (envy-free).
    Mechanisms satisfying each requirement separately have been studied
    extensively, but there are few results on mechanisms achieving both.

  6. Truth and Envy in Capacitated Allocation Games.

    Tue, 03/30/2010 - 15:02 — SomNambul
    Authors: Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky
    Subjects: Computer Science and Game Theory
    Abstract

    We study auctions with additive valuations where agents have a limit on the
    number of items they may receive. We refer to this setting as {\em capacitated
    allocation games.} We seek truthful and envy free mechanisms that maximize the
    social welfare. {\sl I.e.}, where agents have no incentive to lie and no agent
    seeks to exchange outcomes with another. In 1983, Leonard showed that VCG with
    Clarke Pivot payments (which is known to be truthful, individually rational,
    and have no positive transfers), is also an envy free mechanism for the special
    case of $n$ items and $n$ unit capacity agents.

  7. Envy-Free Makespan Approximation.

    Tue, 09/08/2009 - 12:16 — SomNambul
    Authors: Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky
    Subjects: Computer Science and Game Theory
    Abstract

    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 approximates the minimal
    makespan to within a factor of $O(\log m)$, where $m$ is the number of
    machines. We also show a lower bound of $\Omega(\log m / \log\log m)$. This
    improves the recent result of Hartline {\sl et al.} \cite{Ahuva:2008} who give
    an upper bound of $(m+1)/2$, and a lower bound of $2-1/m$.

Math-arch

Syndicate content