Accueil

Edith Cohen

  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. 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.

  4. 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.

  5. 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