The goal of a resource assignment problem is to satisfy a sequence of requests for a limited number of resources. Traditionally, online algorithms have been used to solve these problems, however there has been interes...
详细信息
ISBN:
(纸本)0970789017
The goal of a resource assignment problem is to satisfy a sequence of requests for a limited number of resources. Traditionally, online algorithms have been used to solve these problems, however there has been interest recently in semi-online algorithms, specifically lookahead algorithms. We explore the advantages of lookahead when applied to job scheduling, a representative resource assignment problem. We show results in three areas. First, we develop an original model for lookahead job scheduling on multiple processors in a real-time framework. Second, we,show competitive analysis of some scheduling algorithms developed using the lookahead model. Third, we describe in detail a lookahead algorithm for a two-processor system, show that the algorithm can make each scheduling decision in near-constant time, and evaluate the average-case performance of the algorithm through simulation. Our results demonstrate that lookahead algorithms consistently produce better schedules than online algorithms with little cost in addition. to a built-in lookahead mechanism.
Recent work in dynamic graph algorithms has led to efficient algorithms for dynamic undirected graph problems such as connectivity. However, no efficient deterministic algorithms are known for the dynamic versions of ...
详细信息
Recent work in dynamic graph algorithms has led to efficient algorithms for dynamic undirected graph problems such as connectivity. However, no efficient deterministic algorithms are known for the dynamic versions of fundamental directed graph problems like strong connectivity and transitive closure, as well as some undirected graph problems such as maximum matchings and cuts. We provide some explanation for this lack of success by presenting quadratic lower bounds on the certificate complexity of the seemingly difficult problems, in contrast to the known linear certificate complexity for the problems which have efficient dynamic algorithms. In many applications of dynamic (di)graph problems, a certain form of lookahead is available. Specifically, we consider the problems of assembly planning in robotics and the maintenance of relations in databases. These give rise to dynamic strong connectivity and dynamic transitive closure problems, respectively. We explain why it is reasonable, and indeed natural and desirable, to assume that lookahead is available in these two applications. Exploiting lookahead to circumvent their inherent complexity, we obtain efficient dynamic algorithms for strong connectivity and transitive closure.
暂无评论