Please use this identifier to cite or link to this item:
Title: On the k-truck scheduling problem
Authors: Ma, WM
Xu, YF
You, J 
Liu, J
Wang, KL
Keywords: K-truck problem
On-line algorithm
Competitive ratio
Position maintaining strategy
Partial-greedy algorithm
Issue Date: 2004
Publisher: World Scientific Publ Co Pte Ltd
Source: International Journal of Foundations of Computer Science, 2004, v. 15, no. 1, p. 127-141 How to cite?
Journal: International Journal of Foundations of Computer Science 
Abstract: In this paper, some results concerning the k-truck problem are produced. Firstly, the algorithms and their complexity concerning the off-line k-truck problem are discussed. Following that, a lower bound of competitive ratio (1 + 0) (.) k/(o (.) k + 2) for the on-line k-truck problem is given, where theta is the ratio of cost of the loaded truck and the empty truck on the same distance, and a relevant lower bound for the on-line k-taxi problem followed naturally. Thirdly, based on the Position Maintaining Strategy (PMS), some new results which are slightly better than those of [11] for general cases are obtained. For example, a c-competitive or (c/theta + 1/theta +1)-competitive algorithm for the on-line k-truck problem depending on the value of theta, where c is the competitive ratio of some algorithm to a relevant k-server problem, is developed. The Partial-Greedy Algorithm (PG) is used as well to solve this problem on a line with n nodes and is proved to be a (1 + (n - k)/theta)-competitive algorithm for this case. Finally, the concepts of the on-line k-truck problem are extended to obtain a new variant: Deeper On-line k-Truck Problem (DTP). We claim that results of PMS for the STP (Standard Truck Problem) hold for the DTP.
Description: 8th Annual International Conference on Computing and Combinatorics, Singapore, 15-17 August 2002
ISSN: 0129-0541
DOI: 10.1142/S0129054104002340
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Nov 13, 2018


Last Week
Last month
Citations as of Nov 12, 2018

Page view(s)

Last Week
Last month
Citations as of Nov 11, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.