Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/33830
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
URI: http://hdl.handle.net/10397/33830
ISSN: 0129-0541
DOI: 10.1142/S0129054104002340
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

9
Citations as of Oct 17, 2017

WEB OF SCIENCETM
Citations

9
Last Week
0
Last month
Citations as of Oct 16, 2017

Page view(s)

62
Last Week
5
Last month
Checked on Oct 16, 2017

Google ScholarTM

Check

Altmetric



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