Sandra S. Irani

Assistant Professor, Theory
Donald Bren School of Information and Computer Sciences

Phone: (949) 824-6346
Fax: (949) 824-4056

University of California, Irvine
CS 360B
Mail Code: 3425
Irvine, CA 92697
Research Interests
Design and Analysis of Algorithms
Research Abstract
Dr. Irani's principal research interests are in the design and analysis of algorithms. In particular, most of her research has been in the area of on-line algorithms. The term 'on-line' refers to a relationship between the input stream and the output stream of an algorithm. Namely, the input is presented to the algorithm incrementally and the algorithm must produce part of the output with limited information about the problem. The question is then what kind of solution quality can one hope to obtain? Many problems that arise in Computer Science are on-line problems. Among these are processor scheduling, data structure management, robot motion planning, and resource allocation. Dr. Irani has worked on problems in on-line data structures, graph coloring, scheduling and paging.
Her research uses a new technique called Competitive Analysis which is used to analyze on-line algorithms by comparing the performance of an on-line algorithm to the optimal off-line algorithm. This technique has been useful in that it gives the ability to make strong theoretical statements about the performance of algorithms without making probabilistic assumptions about the input. However, because competitive analysis uses the worst case over every possible input, it can yield results that are more pessimistic than what one observes in practice. In the case of the paging problem, for example, the competitive analysis does not take into account that request sequences generated by programs exhibit locality of reference. Dr. Irani and her co-authors have addressed this problem by formulating a model of locality of reference. They use a graph, called an access graph to define the set of request sequences that can be generated by a particular program. Thus an algorithm can be analyzed on only relevant inputs.

Her recent work has extended the use of competitive analysis to study problems where decisions must be made with partial information due to the fact that a problem is being solved in a distributed setting. The use of competitive analysis allows one to measure the value of shared information. The specific problems addressed in the model are load balancing and network routing. In addition, she has worked on analyzing multiprocessor scheduling and virtual circuit routing, specifically studying how well the performance of a system can be enhanced by allowing the scheduling algorithm to preempt jobs in the middle of execution.
R. Canetti, S. Irani. "Bounding the Power of Preemption in Randomized Scheduling.'' In Proceedings for the 27th Symposium on the Theory of Computing, pp. 606-615, 1995.
S. Irani, Y. Rabani, "On the Value of Information in Coordination Games'', Proceedings for the 34th Symposium on the Foundations of Computer Science and SIAM Journal of Computation, October 1993.
S. Irani, A. Karlin, and S. Phillips, "Strongly Competitive Algorithms for Paging with Locality of Reference", Proceedings for the 3rd Symposium on Discrete Algorithms, pp. 228-236, 1992, To appear in SIAM Journal of Computation.
Last updated