38 citations · 97 across the 11 of their papers we have counts for
5 papers · 1 filter
On the Set Multi-Cover Problem in Geometric Settings
Chandra Chekuri, Kenneth L. Clarkson, Sariel Har-Peled
We consider the set multi-cover problem in geometric settings. Given a set of points P and a collection of geometric shapes (or sets) F, we wish to find a minimum cardinality subse…
Dependent Randomized Rounding for Matroid Polytopes and Applications
Chandra Chekuri, Jan Vondrak, Rico Zenklusen
Motivated by several applications, we consider the problem of randomly rounding a fractional solution in a matroid (base) polytope to an integral one. We consider the pipage roundi…
Longest Wait First for Broadcast Scheduling
Chandra Chekuri, Sungjin Im, Benjamin Moseley
We consider online algorithms for broadcast scheduling. In the pull-based broadcast model there are unit-sized pages of information at a server and requests arrive online for p…
Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling
Chandra Chekuri, Sungjin Im, Benjamin Moseley
We consider online algorithms for pull-based broadcast scheduling. In this setting there are n pages of information at a server and requests for pages arrive online. When the serve…
A Graph Reduction Step Preserving Element-Connectivity and Applications
Chandra Chekuri, Nitish Korula
Given an undirected graph G=(V,E) and subset of terminals T \subseteq V, the element-connectivity of two terminals u,v \in T is the maximum number of u-v paths that are pairwise di…