Search

Abstract: We study an on-line machine covering problem, in which jobs arrive one by one and their processing times are known upon their arrival, and jobs are allowed to migrate between machines when a new job is added in the system. However, the total processing time of migration induced by an incoming job is bounded by a constant factor times the processing time of the incoming job. The objective is to maximize the minimum machine load. In this paper, we present an on-line algorithm with competitive ratio 6/5 for the two identical machines case with . Moreover, the presented on-line algorithm is only a local migration, that is, when one job is assigned to machine , only the jobs on machine are allowed to migrate. We also show that the provided algorithm is a best possible on-line algorithm in the sense of local migration. [Copyright &y& Elsevier]

Abstract: The recently published edge- and lookup table-based inverse halftoning (ELIH) algorithm has shown its quality and superiority when compared with the previous lookup table-based IH algorithm. This paper presents a new finite state machine model (FSMM)-based search method to speed up the existing ELIH algorithm significantly while preserving the same image quality as in the ELIH algorithm. From the observation that the sliding window for the ELIH algorithm moves from left to right one position; there are therefore one output column and one input column which are introduced at each step and thus a simple finite state machine can track the transitions from the current window movement to the next. This is faster than a full search in the lookup table. Under thirty typical testing images adopted from Meşe’s website, experimental results demonstrated that the proposed FSMM-based ELIH algorithm has an improvement in execution time of 20% to 80%, with a typical improvement of 50%, when compared to the ELIH algorithm. [Copyright &y& Elsevier]