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

点击翻译按钮获取中文摘要

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.