Weighted caching is a generalization of paging in which the cost to evict an item depends on the item. We study both of these problems as restrictions of the well-known k-server problem, which involves moving servers in a graph in response to requests so as to minimize the distance traveled. We give a deterministic on-line strategy for weighted caching that, on any sequence of requests, given a cache holding k items, incurs a cost within a factor of k/(k-h+1) of the minimum cost possible given a cache holding h items. The strategy generalizes "least recently used," one of the best paging strategies in practice. The analysis is a primal-dual analysis, the first for an on-line problem, exploiting the linear programming structure of the k-server problem. We introduce loose competitiveness, motivated by Sleator and Tarjan's complaint [ST] that the standard competitive ratios for paging strategies are too high. A k-server strategy is looselyc(k)-competitive if, for any sequence, for almost all k, the cost incurred by the strategy with k servers either is no more than c(k) times the minimum cost or is insignificant. We show that certain paging strategies (including "least recently used," and "first in first out") that are k-competitive in the standard model are loosely c(k)-competitive provided c(k)/In k→∞ and both k/c(k) and c(k) are nondecreasing. We show that the marking algorithm, a randomized paging strategy that is Θ(In k)-competitive in the standard model, is loosely c(k)-competitive provided k-2 In In k→∞ and both 2 In k-c(k) and c(k) are nondecreasing. © 1994 Springer-Verlag New York Inc.

We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous tradeoff: given the two trees and a γ>0, the algorithm returns a spanning tree in which the distance between any vertex and the root of the shortest-path tree is at most 1+√2γ times the shortest-path distance, and yet the total weight of the tree is at most 1+√2/γ times the weight of a minimum spanning tree. Our algorithm runs in linear time and obtains the best-possible tradeoff. It can be implemented on a CREW PRAM to run a logarithmic time using one processor per vertex. © 1995 Springer-Verlag New York Inc.

We give an efficient deterministic parallel approximation algorithm for the minimum-weight vertex- and set-cover problems and their duals (edge/element packing). The algorithm is simple and suitable for distributed implementation. It fits no existing paradigm for fast, efficient parallel algorithms-it uses only “local„ information at each step, yet is deterministic. (Generally, such algorithms have required randomization.) The result demonstrates that linear-programming primal-dual approximation techniques can lead to fast, efficient parallel algorithms. The presentation does not assume knowledge of such techniques. © 1994 Academic Press, Inc.

We study the problem of selecting control clones in DNA array hybridization experiments. The problem arises in the OFRG method for analyzing microbial communities. The OFRG method performs classification of rRNA gene clones using binary fingerprints created from a series of hybridization experiments, where each experiment consists of hybridizing a collection of arrayed clones with a single oligonucleotide probe. This experiment produces analog signals, one for each clone, which then need to be classified, that is, converted into binary values 1 and 0 that represent hybridization and non-hybridization events. Besides the sample clones, the array contains a number of control clones needed to calibrate the classification procedure of the hybridization signals. These control clones must be selected with care to optimize the classification process. We formulate this as a combinatorial optimization problem called Balanced Covering. We prove that the problem is NP-hard and we show some results on hardness of approximation. We propose an approximation algorithm based on randomized rounding and we show that, with high probability, it approximates well the optimum. The experimental results confirm that the algorithm finds high quality control clones. The algorithm has been implemented and is publicly available as part of the software package called CloneTools.