Search

We consider the incremental version of the k-Facility Location Problem, which is a common generalization of the facility location and the k-median problems. The objective is to produce an incremental sequence of facility sets F⊆ F⊆ ⋅⋅⋅⊆ F, where each F contains at most k facilities. An incremental facility sequence or an algorithm producing such a sequence is called c -competitive if the cost of each F is at most c times the optimum cost of corresponding k-facility location problem, where c is called competitive ratio. In this paper we present two competitive algorithms for this problem. The first algorithm produces competitive ratio 8 α, where α is the approximation ratio of k-facility location problem. By recently result (Zhang, Theor. Comput. Sci. 384:126–135, ), we obtain the competitive ratio $16+8\sqrt{3}+\epsilon$ . The second algorithm has the competitive ratio Δ+1, where Δ is the ratio between the maximum and minimum nonzero interpoint distances. The latter result has its self interest, specially for the small metric space with Δ≤8 α−1. [ABSTRACT FROM AUTHOR]

This paper considers the on-line problem of scheduling nonpreemptively n independent jobs on m > 1 identical and parallel machines with the objective to maximize the minimum machine completion time. It is assumed that the values of the processing times are unknown but the order of the jobs by their processing times is known in advance. We are asked to decide the assignment of all the jobs to some machines at time zero by utilizing only ordinal data rather than the actual magnitudes of jobs. Algorithms to slove the problem are called ordinal algorithms. In this paper, we give lower bounds and ordinal algorithms. We first propose an algorithm MIN which is at most $$(\left\lceil {\sum {_{i = 1}^m {\text{ }}1/} i} \right\rceil + 1)$$ -competitive for any m machine case, while the lower bound is ∑ 1/i. Both are on the order of Θ(ln m). Furthermore, for m = 3, we present an optimal algorithm. [ABSTRACT FROM AUTHOR]

The optimization versions of the 3-Partitioning and the Kernel 3-Partitioning problems are considered in this paper. For the objective to maximize the minimum load of the m subsets, it is shown that the MODIFIED LPT algorithm has performance ratios (3 m − 1)/(4 m − 2) and (2 m − 1)/(3 m − 2), respectively, in the worst case. [ABSTRACT FROM AUTHOR]