Bin stretching revisited |
| |
Authors: | Leah Epstein |
| |
Affiliation: | (1) School of Computer Science, The Interdisciplinary Center, Herzliya, Israel (e-mail: lea@idc.ac.il) , IL |
| |
Abstract: | We study three on-line models of bin stretching on two machines. For the case where the machines are identical and the jobs
arrive sorted by non-increasing sizes, we show a tight bound of 10/9 on the competitive ratio. For two related machines, we
show a preemptive algorithm with competitive ratio 1 for any speed ratio, and two new non-preemptive algorithms. We prove
that the upper bound on the competitive ratio achieved by the non-preemptive algorithms is optimal for almost any speed ratio,
and close to optimal for all other speed ratios.
Received: 14 February 2002 / 18 November 2002
Research supported in part by the Israel Science Foundation, (grant No. 250/01-1). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|