28 citations · 244 across the 83 of their papers we have counts for
4 papers · 1 filter
Improved Bounds for Geometric Permutations
Natan Rubin, Haim Kaplan, Micha Sharir
We show that the number of geometric permutations of an arbitrary collection of pairwise disjoint convex sets in , for , is , improvin…
A Kinetic Triangulation Scheme for Moving Points in The Plane
Haim Kaplan, Natan Rubin, Micha Sharir
We present a simple randomized scheme for triangulating a set of points in the plane, and construct a kinetic data structure which maintains the triangulation as the points…
On the Interplay between Incentive Compatibility and Envy Freeness
Edith Cohen, Michal Feldman, Amos Fiat +2
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 t…
Truth and Envy in Capacitated Allocation Games
Edith Cohen, Michal Feldman, Amos Fiat +2
We study auctions with additive valuations where agents have a limit on the number of goods they may receive. We refer to such valuations as {\em capacitated} and seek mechanisms t…