In Information Technology decisions must typically be made before all inputs are available. Whether it is setting up virtual circuits in order to carry IP traffic over ATM networks, deciding whether to leave a disk spinning in between accesses to data, or keeping cache coherent in a multiprocessor architecture -- online algorithms play a crucial role in such diverse areas as machine learning, robotics, operating systems, network routing, distributed systems, databases. It is somewhat surprising that despite such need for online algorithms in Information Technology many fundamental problems remain open.
Many problems under investigation are from a 2002 Dagstuhl Workshop on online algorithms, where, in an open problems session, those problems were selected, whose solution were considered to have greatest impact. The investigators focus on these and other problems, some of which represent long-standing challenges in computer science, and whose solution are likely to have enormous impact on Information Technology.
The investigators, who have a record of successful research in the area of online algorithms, as well as in other areas of computer science, give substantial effort to cracking some of the hardest outstanding open problems in the area, not by seeking ad hoc techniques, but by developing general tools. A new tool that is used in this project is the concept of knowledge states, which had not been previously formulated by other researchers. In addition to investigating online algorithms in the usual models, the investigators consider other models that involve restrictions on computation resources or information flow, such as tracklessness, limited memory, and limited computational time. These restrictions are intended to model real-life constraints.
The investigators concentrate their efforts specifically on the following problems: the deterministic k-server problem for k = 3, the randomized k-server problem for k = 2, the metrical task system problem, the CNN problem, and the cache problem. The investigators examine some additional online problems, such as the weighted server problem, the weighted cache problem, and online scheduling.
This research activity aims at significant advancement of knowledge and understanding across a broad area. The investigators are especially seeking a better understanding of the true nature of online randomization. Online algorithms are needed for an enormous variety of practical situations, in fact, most real-life problems require online algorithms, as decisions must typically be made before all inputs are available. Very wide application of the techniques is expected.
Broader Impacts: The project seeks to strengthen UNLV as a center for undergraduate and graduate student education in theoretical computer science for Nevada, which as an EPSCOR state has limited funding. In the past, NSF funding has enabled students from Southern Nevada, and especially women and other underrepresented groups to pursue theory at UNLV, and it is important for UNLV to further gain momentum in this area. As in the past, the results of this research are used as teaching material in courses at UNLV. More importantly, a substantial quantity of the material is being made available on the World Wide Web in the form of tutorials, where it is available broadly across the network, especially to non-traditional students. The results are to be disseminated in conferences and society will benefit as the online techniques the investigators develop are applied to many areas, including computer networking, memory management, and databases.
