ITR: Online Algorithms and Information Technology

ITR：在线算法和信息技术

• 批准号: 0312093
• 负责人: Wolfgang Bein
• 金额: $ 30万
• 依托单位: University of Nevada Las Vegas
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-08-15 至 2007-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0312093&HistoricalAwards=false
• 关键词: ITR; Online; Algorithms; Information; Technology

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.

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