Search

Abstract: This paper considers two semi-online scheduling problems, one with known optimal value and the other with known total sum, on two uniform machines with a machine speed ratio of . For the first problem, we provide an optimal algorithm for , and improved algorithms or/and lower bounds for , over which the optimal algorithm is unknown. As a result, the largest gap between the competitive ratio and the lower bound decreases to 0.02192. For the second problem, we also present algorithms and lower bounds for . The largest gap between the competitive ratio and the lower bound is 0.01762, and the length of the interval over which the optimal algorithm is unknown is 0.47382. Our algorithms and lower bounds for these two problems provide insights into their differences, which are unusual from the viewpoint of the known results on these two semi-online scheduling problems in the literature. [Copyright &y& Elsevier]

Abstract: The first complete running time analysis of a stochastic divide and conquer algorithm was given for Quicksort, a sorting algorithm invented 1961 by Hoare. We analyse here the variant Random Median Quicksort. The analysis includes the expectation, the asymptotic distribution, the moments and exponential moments. The asymptotic distribution is characterized by a stochastic fixed point equation. The basic technic will be generating functions and the contraction method. [Copyright &y& Elsevier]

Abstract: In semi-online scheduling problems, we always assume that some partial additional information is exactly known in advance. This may not be true in some applications. This paper considers semi-online scheduling problems on two identical machines with inexact partial information. Three versions are considered, where we know in advance that the total size of all jobs, the optimal value, and the largest job size are in given intervals, respectively, while their exact values are unknown. We give both lower bounds of the problems and competitive ratios of algorithms as functions of a so-called disturbance parameter . We establish for which the inexact partial information is useful to improve the performance of a semi-online algorithm with respect to its pure online problem. Optimal or near optimal algorithms are then obtained. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the k-partitioning problems with partition matroid constraint and present an algorithm called the layered LPT algorithm. With the objective of minimizing the maximum load, we show that the layered LPT algorithm has a tight worst case ratio of . With the objective of maximizing the minimum load, we show that the layered LPT algorithm has a tight worst case ratio of for the general case and, with certain conditions, the worst ratio can be improved to for the general case and to for the case. [Copyright &y& Elsevier]

Abstract: This paper investigates the semi-online version of scheduling problem on a three-machine system. We assume that all jobs have their processing times between p and rp (). We give a comprehensive competitive ratio of LS algorithm which is a piecewise function on . It shows that LS is an optimal semi-online algorithm for every , and . We further present an optimal algorithm for every , and an almost optimal algorithm for every where the largest gap between its competitive ratio and the lower bound of the problem is at most 0.01417. We also present an improved algorithm with smaller competitive ratio than that of LS for every . [Copyright &y& Elsevier]

The optimization versions of the k-PARTITIONING problems are considered in this paper. For the objective to maximize the minimum load of m subsets, we first show that the FOLDING algorithm has a tight worst case ratio of max{2/k,1/m}. Then, we present an algorithm called HARMONIC1 with a worst case ratio at least max{ 1/k, 1/(⌈Σi=1m 1/i ⌉ +1)}. It concludes the HARMONIC1 is better than FOLDING for k > 2(⌈ Σi=1m 1/i ⌉ + 1). We further show that HARMONICI is asymptotically optimal ordinal algorithm. We also present an algorithm HARMONIC2 for solving the general κi-PARTITIONING problem. [Copyright &y& Elsevier]

String matching is the problem of finding all the occurrences of a pattern in a text. We present a new method to compute the combinatorial shift function (“matching shift”) of the well-known Boyer–Moore string matching algorithm. This method implies the computation of the length of the longest suffixes of the pattern ending at each position in this pattern. These values constituted an extra-preprocessing for a variant of the Boyer–Moore algorithm designed by Apostolico and Giancarlo. We give here a new presentation of this algorithm that avoids extra preprocessing together with a tight bound of 1.5n character comparisons (where n is the length of the text). [Copyright &y& Elsevier]

Phase transitions, ubiquitous in condensed matter physics, are encountered in computer science too. The existence of critical phenomena has deep consequences on computational complexity, that is the resolution times of various optimization or decision problems. Concepts and methods borrowed from the statistical physics of disordered and out-of-equilibrium systems shed new light on the dynamical operation of solving algorithms. [Copyright &y& Elsevier]