Research Initiation Award: Algorithms for On-Line and Distributed Systems

这个项目的重点是在线工作或有限信息的算法。该项目涉及三个主题，每个主题都由在线，分布式或并行计算中的应用驱动：(1)任务集（系统输入）受到限制的度量任务系统。对输入的限制是系统描述的一部分。开发了一种通用的、简单的算法，该算法使用系统规格来近似每个特定系统的最佳在线算法；(2)分布式计算，一组智能体必须共同解决一个问题。每个代理接收部分输入，并使用图来表示代理之间共享的知识。如何利用agent之间的共享信息来解决分布式作业调度问题，并确定共享信息的价值；(3)讨论了偏序元素在线划分为不相交链的问题及其在并行计算中的应用。

This project focuses on algorithms that work on-line or with limited information. The project addresses three topics, each motivated by an application in on-line, distributed or parallel computation: (1) 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 general, simple algorithm is developed which uses the system specification to approximate the best on-line algorithm for each particular system; (2) 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. How to use shared information between the agents to solve a distributed job scheduling problem and to determine the value of sharing information are determined; (3) the problem of partitioning elements of a partial order into disjoint chains on-line, and its applications to parallel computation are discussed.