In 2-space bounded model of on-line bin packing, there are 2 active bins, and each item can be packed only into one of the active bins. If it is impossible to pack an item into any active bin, we close one of the curr...
详细信息
In 2-space bounded model of on-line bin packing, there are 2 active bins, and each item can be packed only into one of the active bins. If it is impossible to pack an item into any active bin, we close one of the current active bins and open a new active bin to pack that item. In 2-space bounded 2-dimensional bin packing problem, each item is a rectangle of side lengths not greater than 1. The items are packed on-line into square bins of size 1 x 1 and 90 degrees-rotations are allowed. In this paper a 4-competitive 2-space bounded 2-dimensional on-line packing algorithm is presented. Furthermore, an on-line strategy with competitive ratio 3.8 is given for 2-space bounded square packing. (C) 2012 Elsevier B.V. All rights reserved.
The online version of the dominating set problem is considered in 2 settings. The first setting is that all vertices 1, 2, ..., n in the graph are given in advance. At time interval i the adjacency condition of vert...
详细信息
The online version of the dominating set problem is considered in 2 settings. The first setting is that all vertices 1, 2, ..., n in the graph are given in advance. At time interval i the adjacency condition of vertex i to the other vertices is presented. An online algorithm of performance ratio 1.5 square root of n + c-sub-1 is proposed and it is shown that the square root n - c-sub-2 is a lower bound for the performance ratio that an online dominating set algorithm can possibly achieve, where c-sub-1 and c-sub-2 are some positive constants.
We consider a semi-dynamic setting for the Temporal Constraint Satisfaction Problem (TCSP), where we are requested to maintain the path-consistency of a network under a sequence of insertions of new (further) constrai...
详细信息
We study the on-line version of the maximum independent set problem, for the case of disk graphs which are graphs resulting from intersections of disks on the plane. In particular, we investigate whether randomization...
详细信息
We study the on-line version of the maximum independent set problem, for the case of disk graphs which are graphs resulting from intersections of disks on the plane. In particular, we investigate whether randomization can be used to break known lower bounds for deterministic on-line independent set algorithms and present new upper and lower bounds. (c) 2006 Elsevier B.V. All rights reserved.
In this paper, we consider the problem of on-line scheduling a job sequence on two uniform machines. A job can be either rejected, in which case we pay its penalty, or scheduled on machines, in which case it contribut...
详细信息
In this paper, we consider the problem of on-line scheduling a job sequence on two uniform machines. A job can be either rejected, in which case we pay its penalty, or scheduled on machines, in which case it contributes its processing time to the makspan of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule for all accepted jobs and the penalties of all rejected jobs. Both preemptive and non-preemptive versions are considered. For the preemptive version, we present an optimal on-line algorithm with a competitive ratio 1/2 + root 1/4 + 1/s for any s >= 1, where s is the machine speed ratio. For the non-preemptive version, we present an improved lower bound. Moreover, as an optimal algorithm for s >= 1.6180 is known, we present a modified version of the known algorithm, and show that it becomes optimal for any 1.3852 <= s < 1.6180 and has a smaller competitive ratio than that of original version for any 1 <= s < 1.3852. The maximum gap between its competitive ratio and the lower bound is 0.0534.
We consider the sequencing of a series of jobs that arrive at a single processor over time. At each job's arrival time, a due date must be quoted for the job, and the job must complete processing before its quoted...
详细信息
We consider the sequencing of a series of jobs that arrive at a single processor over time. At each job's arrival time, a due date must be quoted for the job, and the job must complete processing before its quoted due date. The objective is to minimize the sum (or average) of quoted due dates, or equivalently, the average quoted lead time. In this paper, we propose on-line heuristics for this problem and characterize the conditions under which these heuristics are asymptotically optimal. Computational testing further demonstrates the relative effectiveness of these heuristics under various conditions.
The partition problem is one of the basic NP-complete problems. While an efficient heuristic for the optimization version, which is equivalent to minimizing the makespan on two identical machines, is known with worst-...
详细信息
The partition problem is one of the basic NP-complete problems. While an efficient heuristic for the optimization version, which is equivalent to minimizing the makespan on two identical machines, is known with worst-case ratio 12/11, no deterministic heuristic for the on-line problem can have a worst-case ratio lower than 3/2 In this paper we investigate three different semi on-line versions of the partition problem. In the first case, we assume that a buffer of length k is available to maintain k items. In the second case, two parallel processors are available which assign each item independently to the partition sets. The best of the two produced solutions is chosen. Finally, in the third problem the total sum of the items is known in advance. For each version we propose a heuristic and investigate its worst-case ratio. All algorithms have a worst-case ratio of which is shown to be the best possible worst-case ratio. (C) 1997 Elsevier Science B.V. All rights reserved.
Competitive on-line algorithms for data management in a network of processors are studied in this paper. A data object such as a file or a page of virtual memory is to be read and updated by various processors in the ...
详细信息
Competitive on-line algorithms for data management in a network of processors are studied in this paper. A data object such as a file or a page of virtual memory is to be read and updated by various processors in the network. The goal is to minimize the communication costs incurred in serving a sequence of such requests. Distributed data management on important classes of networksd. Optimal algorithms with constant competitive ratios and matching lower bounds are obtained. Our algorithms use different interesting techniques, such as work functions [Chrobak and Larmore, Proc. DIMACS Workshop on on-line algorithms, AMS, 1991, pp. 11-64] and "factoring."
In this paper we define on-line algorithms for neural-network training, based on the construction of multiple copies of the network, which are trained by employing different data blocks. It is shown that suitable trai...
详细信息
In this paper we define on-line algorithms for neural-network training, based on the construction of multiple copies of the network, which are trained by employing different data blocks. It is shown that suitable training algorithms can be defined, in a way that the disagreement between the different copies of the network is asymptotically reduced, and convergence toward stationary points of the global error function can be guaranteed, Relevant features of the proposed approach are that the learning rate must be not necessarily forced to zero and that real-time learning is permitted.
The best randomized on-line algorithms known so far for the list update problem achieve a competitiveness of root 3 approximate to 1.73. In this paper we present a new family of randomized onlinealgorithms that beat ...
详细信息
The best randomized on-line algorithms known so far for the list update problem achieve a competitiveness of root 3 approximate to 1.73. In this paper we present a new family of randomized onlinealgorithms that beat this competitive ratio. Our improved algorithms are called TIMESTAMP algorithms and achieve a competitiveness of max {2 - p,1 + p(2 - p)}, for any real number p epsilon [0,1]. Setting p = (3 - root 5)/2, we obtain a phi-competitive algorithm, where phi = (1 + root 5)/2 approximate to 1.62 is the golden ratio. TIMESTAMP algorithms coordinate the movements of items using some information on past requests. We can reduce the required information at the expense of increasing the competitive ratio. We present a very simple version of the TIMESTAMP algorithms that is 1.68-competitive. The family of TIMESTAMP algorithms also includes a new deterministic 2-competitive on-line algorithm that is different from the MOVE-TO-FRONT RULE.
暂无评论