Author name cluster

Steve Seiden

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

TCS Journal 2004 Journal Article

Combining request scheduling with web caching

Tomás Feder
Rajeev Motwani
Rina Panigrahy
Steve Seiden
Rob van Stee
An Zhu

We extend the classic paging model by allowing reordering of requests under the constraint that a request is delayed by no longer than a predetermined number of time steps. We first give a dynamic programming algorithm to solve the offline case. Then we give tight bounds on competitive ratios for the online case. For caches of size k, we obtain bounds of k+O(1) for deterministic algorithms and Θ(log k) for randomized algorithms. We also give bounds for the case where either the online or the offline algorithm can reorder the requests, but not both. Finally, we extend our analysis to the case where pages have different sizes.

Details DOI

TCS Journal 2004 Journal Article

New results for online page replication

Rudolf Fleischer
Włodzimierz Głazek
Steve Seiden

We study the online page replication problem. We present a new randomized online algorithm for rings which is 2. 37297-competitive, improving the best previous result of 3. 16396. We also show that no randomized online algorithm is better than 1. 75037-competitive on the ring; previously, only a 1. 58198 bound for a single edge was known. We extend the problem in several new directions: continuous metrics, variable size requests, and replication before service. This yields simplified proofs of several known results.

Details DOI

TCS Journal 2002 Journal Article

A manifesto for the computational method

Steve Seiden

We promote the much maligned computational method. The computational method is a paradigm for proving mathematical results where the burden of doing the “grunt work” is given to our able research assistant, the computer. We assert that proofs using the computational method, also known as computer aided proofs, are here to stay. In fact, the use of a computer can make the analysis of complicated algorithms fun. We illustrate the usefulness of the method by analyzing a randomized algorithm for multi-processor scheduling with rejection. More specifically, we present a randomized algorithm which is 1. 44127-competitive. The best previously known result is a 1. 5-competitive algorithm.

Details DOI

I&C Journal 1999 Journal Article

Unfair Problems and Randomized Algorithms for Metrical Task Systems

Steve Seiden

Borodin, Linial, and Saks introduced a general model for online systems calledmetrical task systems(1992, J. Assoc. Comput. Mach. 39(4), 745–763). In this paper, the unfair two state problem, a natural generalization of the two state metrical task system problem, is studied. A randomized algorithm for this problem is presented, and it is shown that this algorithm is optimal. Using the analysis of the unfair two state problem, a proof of a decomposition theorem similar to that of Blum, Karloff, Rabani, and Saks (1992, “Proc. 33rd Symposium on Foundations of Computer Science, ” pp. 197–207) is presented. This theorem allows one to design divide and conquer algorithms for specific metrical task systems. Our theorem gives the same bounds asymptotically, but it has less restrictive boundary conditions.

Details DOI

TCS Journal 1998 Journal Article

Randomized algorithms for metrical task systems

Sandy Irani
Steve Seiden

Borodin et al. (1992) introduce a general model for online systems in [3] called task systems and show a deterministic algorithm which achieves a competitive ratio of 2n − 1 for any metrical task system with n states. We present a randomized algorithm which achieves a competitive ratio of e/(e − 1)n − 1/(e − 1) ≈ 1. 5820n − 0. 5820 for this same problem. For the uniform metric space, Borodin et al. present an algorithm which achieves a competitive ratio of 2H n, and they show a lower bound of H n, for any randomized algorithm. We improve their upper bound for the uniform metric space by showing a randomized algorithm which is (H n + O(√log n))-competitive.

Details DOI