For a positive integer k, let k + k denote the poset consisting of two disjoint k-element chains, with all points of one chain incomparable with all points of the other. Bosek, Krawczyk and Szczypka showed that for ea...
详细信息
For a positive integer k, let k + k denote the poset consisting of two disjoint k-element chains, with all points of one chain incomparable with all points of the other. Bosek, Krawczyk and Szczypka showed that for each k a parts per thousand yenaEuro parts per thousand 1, there exists a constant c (k) so that First Fit will use at most chains in partitioning a poset P of width at most w, provided the poset excludes k + k as a subposet. This result played a key role in the recent proof by Bosek and Krawczyk that O(w (16logw) ) chains are sufficient to partition on-line a poset of width w into chains. This result was the first improvement in Kierstead's exponential bound: (5 (w) -aEuro parts per thousand 1)/4 in nearly 30 years. Subsequently, Joret and Milans improved the Bosek-Krawczyk-Szczypka bound for the performance of First Fit to 8(k -aEuro parts per thousand 1)(2) w, which in turn yields the modest improvement to O(w (14logw) ) for the general on-line chain partitioning result. In this paper, we show that this class of posets admits a notion of on-line dimension. Specifically, we show that when k and w are positive integers, there exists an integer t = t(k,w) and an on-line algorithm that will construct an on-line realizer of size t for any poset P having width at most w, provided that the poset excludes k + k as a subposet.
The on-line planarity-testing problem consists of performing the following operations on a planar graph G: (i) testing if a new edge can be added to G so that the resulting graph is itself planar;(ii) adding vertices ...
详细信息
The on-line planarity-testing problem consists of performing the following operations on a planar graph G: (i) testing if a new edge can be added to G so that the resulting graph is itself planar;(ii) adding vertices and edges such that planarity is preserved. An efficient technique for online planarity testing of a graph is presented that uses O(n) space and supports tests and insertions of vertices and edges in O(log n) time, where n is the current number of vertices of G. The bounds for tests and vertex insertions are worst-case and the bound for edge insertions is amortized. We also present other applications of this technique to dynamic algorithms for planar graphs.
Consider the execution of a parallel application that dynamically generates parallel jobs with specified resource requirements during its execution. We assume that there is not sufficient knowledge about the running t...
详细信息
Consider the execution of a parallel application that dynamically generates parallel jobs with specified resource requirements during its execution. We assume that there is not sufficient knowledge about the running times and the number of jobs generated in order to precompute a schedule for such applications. Rather, the scheduling decisions have to be made on-line during runtime based on incomplete information. We present several on-line scheduling algorithms for various interconnection topologies that use some a priori information about the job running times or guarantee a good competitive ratio that depends on the runtime ratio of all generated jobs. All algorithms presented have optimal competitive ratio up to small additive constants, and are easy to implement. (C) 2001 Elsevier Science B.V. All rights reserved.
Given a directed graph G=(V,E), it is supposed that edges are added to or deleted from G one at a time, and that one wishes to compute its transitive closure in the online manner, i.e., each time an edge is added or d...
详细信息
Given a directed graph G=(V,E), it is supposed that edges are added to or deleted from G one at a time, and that one wishes to compute its transitive closure in the online manner, i.e., each time an edge is added or deleted. In the case of an undirected graph, G, the problem of online computation of connected components of G has been comprehensively studied. However, no nontrivial onlinealgorithm for computing the transitive closure of general directed graphs has been reported. Online transitive closure algorithms are presented for 2 problems: 1. q edges are successively added to G=(V,E), and 2. q edges are successively deleted from G=(V,E).
In this paper, we consider a two-dimensional version of the on-line bin packing problem, in which each rectangular item that should be packed into unit square bins is "rotatable" by 90degrees. Two on-line al...
详细信息
In this paper, we consider a two-dimensional version of the on-line bin packing problem, in which each rectangular item that should be packed into unit square bins is "rotatable" by 90degrees. Two on-line algorithms for solving the problem are proposed. The second algorithm is an extension of the first algorithm, and the worst-case ratio of the second one is at least 2.25 and at most 2.565. (C) 2002 Elsevier Science B.V. All rights reserved.
In this paper, some results concerning the k-truck problem are produced. Firstly, the algorithms and their complexity concerning the off-line k-truck problem are discussed. Following that, a lower bound of competitive...
详细信息
In this paper, some results concerning the k-truck problem are produced. Firstly, the algorithms and their complexity concerning the off-line k-truck problem are discussed. Following that, a lower bound of competitive ratio (1 + 0) (.) k/(o (.) k + 2) for the on-line k-truck problem is given, where theta is the ratio of cost of the loaded truck and the empty truck on the same distance, and a relevant lower bound for the on-line k-taxi problem followed naturally. Thirdly, based on the Position Maintaining Strategy (PMS), some new results which are slightly better than those of [11] for general cases are obtained. For example, a c-competitive or (c/theta + 1/theta +1)-competitive algorithm for the on-line k-truck problem depending on the value of theta, where c is the competitive ratio of some algorithm to a relevant k-server problem, is developed. The Partial-Greedy algorithm (PG) is used as well to solve this problem on a line with n nodes and is proved to be a (1 + (n - k)/theta)-competitive algorithm for this case. Finally, the concepts of the on-line k-truck problem are extended to obtain a new variant: Deeper On-line k-Truck Problem (DTP). We claim that results of PMS for the STP (Standard Truck Problem) hold for the DTP.
We study the worst-case performance of approximation algorithms for the problem of multiprocessor task scheduling on m, identical processors with resource augmentation, whose objective is to minimize the makespan. In ...
详细信息
We study the worst-case performance of approximation algorithms for the problem of multiprocessor task scheduling on m, identical processors with resource augmentation, whose objective is to minimize the makespan. In this case, the approximation algorithms are given k (k >= 0) extra processors than the optimal off-linealgorithm. For on-line algorithms, the Greedy algorithm and shelf algorithms are studied. For off-linealgorithm, we consider the LPT (longest processing time) algorithm. Particularly, we prove that the schedule produced by the LPT algorithm is no longer than the optimal off-linealgorithm if and only if k >= m - 2.
In the on-line rescheduling on a single machine, a set of original jobs has already been scheduled to minimize some cost objective, when a new set of jobs arrives over time. The decision maker needs to insert the new ...
详细信息
ISBN:
(纸本)9780769537788
In the on-line rescheduling on a single machine, a set of original jobs has already been scheduled to minimize some cost objective, when a new set of jobs arrives over time. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. In this paper, we consider the on-line rescheduling problem to minimize makespan under a limit on the maximum disruption constraints and give an on-line algorithm of competitive ratio 3/2.
This paper studies the on-line supply chain scheduling problem for single machine with multiple customers under the constraint of the unlimited number of vehicles but limited vehicle capacity. The customers place thei...
详细信息
This paper studies the on-line supply chain scheduling problem for single machine with multiple customers under the constraint of the unlimited number of vehicles but limited vehicle capacity. The customers place their orders on-line, which means that no information of future jobs is known beforehand. The jobs are processed on a single machine and then delivered to the customers by vehicles. Every vehicle can only contain the jobs of the same customer and every batch has the same fixed cost. The objective of the scheduling is to minimize the total makespan and the total delivery cost. Such a problem is called on-line problem. An on-line algorithm for the problem is designed, which is proved to be 2 + 1/2-competitive. The paper also presents a case study for demonstrating the robustness and efficiency of the algorithm. (C) 2015, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.
This paper presents an on-line algorithm for the construction of position trees, i.e., an algorithm which constructs the position tree for a given string while reading the string from left to right. In addition, an on...
详细信息
This paper presents an on-line algorithm for the construction of position trees, i.e., an algorithm which constructs the position tree for a given string while reading the string from left to right. In addition, an on-line correction algorithm is presented which—upon a change in the string—can be used to construct the new position tree. Moreover, special attention is paid to computers with small memory. compactification of the trees and transport costs between main and secondary storage are discussed.
暂无评论