Competitive Analysis of Online and Distributed Systems (Computer Science)

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

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.