Competitive Analysis of Online and Distributed Systems (Computer Science)

在线和分布式系统的竞争分析（计算机科学）

• 批准号: 9450142
• 负责人: Sandra Irani
• 金额: $ 7.18万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-09-01 至 1995-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9450142&HistoricalAwards=false
• 关键词: Competitive; Analysis; Online; Distributed; Systems

This research focuses on algorithms that work limited information. Three topics are addressed, and each is motivated by an application in online or distributed computation. These topics include: (1) Distributed computation where a group of agents must collectively solve a problem. Each agent receives part of the input, and a graph is used to represent knowledge that is shared between the agents. The goal is to determine how to use shared information between the agents as well as to determine the value of sharing information. (2) These issues will be addressed with respect to problems in distributed job scheduling and network routing. Metrical Task Systems where the set of tasks (inputs to the system) are restricted. The restriction on the input is part of the description of the system. A unified approach will be developed to a variety of online problems by developing a general, simple algorithm which uses the system specification to approximate the best online algorithm for each particular system. (3) The use of a statistical adversary, which provides a way of bringing theoretical results in online algorithms closer to practical concerns by considering only those inputs which exhibit typical statistical features. It is a middle ground between probabilistic analysis and competitive analysis where the input is generated by an unlimited adversary. The use of a statistical adversary for problems in finance and computer systems will be considered. Interactive activities include: teaching a research seminar in online algorithms; leading weekly meetings with computer theory students to discuss research problems; involvement into the Columbia Chapter of the Society of Women Engineers; & women in the Computer Science Department.

这项研究的重点是工作有限的信息的算法。 三个主题的解决，每一个都是由在线或分布式计算的应用程序的动机。 这些主题包括：（1）分布式计算，其中一组代理必须集体解决一个问题。 每个代理接收部分输入，并使用图来表示代理之间共享的知识。 目标是确定如何使用代理之间的共享信息以及确定共享信息的价值。(2)这些问题将在分布式作业调度和网络路由问题方面得到解决。 计量任务系统，其中任务集（系统的输入）受到限制。 对输入的限制是系统描述的一部分。 一个统一的方法将开发各种在线问题，通过开发一个通用的，简单的算法，使用系统规范近似每个特定系统的最佳在线算法。 (3)使用的统计对手，它提供了一种方法，使在线算法的理论结果更接近实际问题，只考虑那些输入表现出典型的统计特征。 它是概率分析和竞争分析之间的中间地带，其中输入是由无限的对手产生的。 将考虑在金融和计算机系统问题的统计对手的使用。 互动活动包括：教授在线算法的研究研讨会;领导每周与计算机理论学生讨论研究问题的会议;参与女工程师协会哥伦比亚分会;&计算机科学系的妇女。