Tracy Kimbrel

SODA Conference 2008 Conference Paper

Online make-to-order joint replenishment model: primal dual competitive algorithms

• Niv Buchbinder
• Tracy Kimbrel
• Retsef Levi
• Konstantin Makarychev
• Maxim Sviridenko

SODA Conference 2005 Conference Paper

Job shop scheduling with unit processing times

• Nikhil Bansal 0001
• Tracy Kimbrel
• Maxim Sviridenko

FOCS Conference 2004 Conference Paper

Dynamic Speed Scaling to Manage Energy and Temperature

• Nikhil Bansal 0001
• Tracy Kimbrel
• Kirk Pruhs

We first consider online speed scaling algorithms to minimize the energy used subject to the constraint that every job finishes by its deadline. We assume that the power required to run at speed s is P(s) = s/sup /spl alpha//. We provide a tight /spl alpha//sup /spl alpha// bound on the competitive ratio of the previously proposed optimal available algorithm. This improves the best known competitive ratio by a factor of 2/sup /spl alpha//. We then introduce an online algorithm, and show that this algorithm's competitive ratio is at most 2(/spl alpha//(/spl alpha/ - 1))/sup /spl alpha//e/sup /spl alpha//. This competitive ratio is significantly better and is approximately 2e/sup /spl alpha/+1/ for large /spl alpha/. Our result is essentially tight for large /spl alpha/. In particular, as /spl alpha/ approaches infinity, we show that any algorithm must have competitive ratio e/sup /spl alpha// (up to lower order terms). We then turn to the problem of dynamic speed scaling to minimize the maximum temperature that the device ever reaches, again subject to the constraint that all jobs finish by their deadlines. We assume that the device cools according to Fourier's law. We show how to solve this problem in polynomial time, within any error bound, using the ellipsoid algorithm.

SODA Conference 2004 Conference Paper

Minimizing migrations in fair multiprocessor scheduling of persistent tasks

• Tracy Kimbrel
• Baruch Schieber
• Maxim Sviridenko

TCS Journal 2001 Journal Article

Online paging and file caching with expiration times

• Tracy Kimbrel

STOC Conference 2001 Conference Paper

Online server allocation in a server farm via benefit task systems

• T. S. Jayram
• Tracy Kimbrel
• Robert Krauthgamer
• Baruch Schieber
• Maxim Sviridenko

A web content hosting service provider needs to dynamically allocate servers in a server farm to its customers' web sites. Ideally, the allocation to a site should always suffice to handle its load. However, due to a limited number of servers and the overhead incurred in changing the allocation of a server from one site to another, the system may become overloaded. The problem faced by the web hosting service provider is how to allocate the available servers in the most profitable way. Adding to the complexity of this problem is the fact that future loads of the sites are either unknown or known only for the very near future. In this paper we model this server allocation problem , and consider both its offline and online versions. We give a polynomial time algorithm for computing the optimal offline allocation. In the online setting, we show almost optimal algorithms (both deterministic and randomized) for any positive lookahead. The quality of the solution improves as the lookahead increases. We also consider several special cases of practical interest. Finally, we present some experimental results using actual trace data that show that one of our online algorithm performs very close to optimal. Interestingly, the online server allocation problem can be cast as a more general benefit task system that we define. Our results extend to this task system, which captures also the benefit maximization variants of the k -server problem and the metrical task system problem. It follows that the benefit maximization variants of these problems are more tractable than their cost minimization variants.

SODA Conference 1999 Conference Paper

Interleaved Prefetching

• Tracy Kimbrel

FOCS Conference 1996 Conference Paper

Near-Optimal Parallel Prefetching and Caching

• Tracy Kimbrel
• Anna R. Karlin

The authors consider algorithms for integrated prefetching and caching in a model with a fixed-size cache and any number of backing storage devices (disks). Previously, the single disk case was considered by Cao et al. (1995). They show that the natural extension of their aggressive algorithm to the parallel disk case is suboptimal by a factor near the number of disks in the worst case. The main result is a new algorithm, reverse aggressive, with near-optimal performance in the presence of multiple disks.