Practical Competitive Analysis (Computer Science)

实用竞争分析（计算机科学）

• 批准号: 9450075
• 负责人: Anna Karlin
• 金额: $ 23.88万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-09-01 至 1996-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9450075&HistoricalAwards=false
• 关键词: Practical; Competitive; Analysis; Computer; Science

An algorithm is said to be online if it receives input in a sequence of requests, and must service each request as it arrives without any knowledge of the future. Many fundamental problems in computer science are inherently online. A commonly used method of analyzing online algorithms is competitive analysis, where the performance of the online algorithm is compared to the performance of the optimal clairvoyant algorithm. There are several practical problems with the usual style of competitive analysis, including the use of worst care adversary, the lack of attention to implementation efficiency, and the lack of empirical evidence concerning the performance of competitive algorithms. The goal of this project is to help bridge the gap between theory and practice in this rapidly growing area by developing efficient, adaptive algorithms for fundamental systems problems. These algorithms should perform well against a statistical adversary, and will be empirically evaluated. Interactive activities include: participation in the mentoring and outreach programs of Women in Engineering; development of and experimentation with software for teaching math to girls, via collaboration with Professor Steve Tanimoto's research group at the University of Washington (UW) and with Professor Maria Klawe's E- GEMS project at the University of British Columbia; and teaching an undergraduate course and seminars in computer science and undertaking joint research with other members of the computer science faculty at UW.

如果一个算法接收一系列请求中的输入，并且必须在每个请求到达时为每个请求提供服务，而对未来一无所知，则该算法被称为在线算法。 计算机科学中的许多基本问题本质上都是在线的。 分析在线算法的常用方法是竞争分析，将在线算法的性能与最佳洞察算法的性能进行比较。 通常的竞争分析方式存在一些实际问题，包括使用最差的对手、缺乏对实施效率的关注以及缺乏有关竞争算法性能的经验证据。 该项目的目标是通过针对基本系统问题开发高效的自适应算法，帮助弥合这一快速发展领域的理论与实践之间的差距。 这些算法在对抗统计对手时应该表现良好，并且将根据经验进行评估。 互动活动包括： 参与工程界女性的指导和外展计划；通过与华盛顿大学 (UW) Steve Tanimoto 教授的研究小组以及不列颠哥伦比亚大学 Maria Klawe 教授的 E-GEMS 项目合作，开发并实验了用于女孩数学教学的软件；教授计算机科学本科课程和研讨会，并与华盛顿大学计算机科学系的其他成员进行联合研究。