Distributed Algorithms for Approximating Wireless Network Capacity (2010)
Abstract—In this paper we consider the problem of maximizing wireless network capacity (a.k.a. one-shot scheduling) in both the protocol and physical models. We give the first distributed...
Secretary Problems: Weights and Discounts (2009)
Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, Kunal Talwar
The classical secretary problem studies the problem of selecting online an element (a “secretary”) with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an...
Matthew Andrews, Michael Dinitz
Abstract—In this paper we consider the problem of maximizing the number of supported connections in arbitrary wireless networks where a transmission is supported if and only if the...
Secretary Problems: Weights and Discounts (2009)
Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, Kunal Talwar
The classical secretary problem studies the problem of selecting online an element (a “secretary”) with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an...
Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics (2009)
Abstract. The theoretical computer science community has traditionally used embeddings of finite metrics as a tool in designing approximation algorithms. Recently, however, there has been...
FULL RANK TILINGS OF FINITE ABELIAN GROUPS ∗ (2008)
Abstract. A tiling of a finite abelian group G is a pair (V,A) of subsets of G such that 0 is in both V and A and every g ∈ G can be uniquely written as g = v + a with v ∈ V and a ∈ A. Tilings...
Secretary problems: Weights and discounts (2008)
Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, Kunal Talwar
The classical secretary problem studies the problem of selecting online an element (a “secretary”) with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an...
T. -h. Hubert Chan, Michael Dinitz, Anupam Gupta
Abstract. Given a metric (V,d), a spanner is a sparse graph whose shortest-path metric approximates the distance d to within a small multiplicative distortion. In this paper, we study the problem of...