ITR: Online Algorithms and Information Technology

在信息技术中，通常必须在所有输入可用之前做出决策。无论是为了在ATM网络上传输IP流量而设置虚拟电路，决定是否在访问数据之间留下磁盘旋转，还是在多处理器架构中保持缓存一致——在线算法在机器学习、机器人、操作系统、网络路由、分布式系统、数据库等不同领域发挥着至关重要的作用。有些令人惊讶的是，尽管信息技术对在线算法有这样的需求，但许多基本问题仍未解决。许多正在调查的问题来自2002年Dagstuhl在线算法研讨会，在一个开放问题会议上，这些问题被选择出来，其解决方案被认为具有最大的影响。研究人员关注这些问题和其他问题，其中一些问题代表了计算机科学的长期挑战，其解决方案可能对信息技术产生巨大影响。这些研究人员在在线算法领域以及计算机科学的其他领域都有成功的研究记录，他们付出了巨大的努力来破解该领域一些最困难的突出开放问题，不是通过寻求特殊技术，而是通过开发通用工具。在这个项目中使用的一个新工具是知识状态的概念，这是其他研究人员以前没有提出的。除了研究通常模型中的在线算法外，研究人员还考虑了其他涉及计算资源或信息流限制的模型，例如无轨迹、有限内存和有限计算时间。这些限制旨在模拟现实生活中的约束。研究人员将他们的努力集中在以下问题上：k = 3时的确定性k-服务器问题，k = 2时的随机k-服务器问题，度量任务系统问题，CNN问题和缓存问题。研究人员还研究了一些附加的在线问题，例如加权服务器问题、加权缓存问题和在线调度。这项研究活动的目的是在一个广泛的领域显著提高知识和理解。研究人员尤其希望更好地理解在线随机化的本质。各种各样的实际情况都需要在线算法，事实上，大多数现实生活中的问题都需要在线算法，因为通常必须在所有输入可用之前做出决策。这些技术有望得到广泛的应用。更广泛的影响：该项目旨在加强UNLV作为内华达州理论计算机科学本科生和研究生教育中心，这是一个EPSCOR国家有限的资金。过去，美国国家科学基金会的资助使来自南内华达州的学生，特别是女性和其他代表性不足的群体能够在UNLV学习理论，对于UNLV来说，在这一领域进一步获得动力非常重要。与过去一样，这项研究的结果被用作UNLV课程的教材。更重要的是，相当数量的材料正以教程的形式在万维网上提供，这些材料在整个网络上广泛提供，特别是对非传统的学生。研究结果将在会议上发布，社会将受益，因为研究人员开发的在线技术将应用于许多领域，包括计算机网络、内存管理和数据库。

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.