TY - GEN

T1 - New results on the k-truck problem

AU - Ma, Weimin

AU - Xu, Yinfeng

AU - You, Jia

AU - Liu, James

AU - Wang, Kanliang

PY - 2002/1/1

Y1 - 2002/1/1

N2 - In this paper, some results concerning the k-truck problem are produced. First, the algorithms and their complexity concerning the off-line k-truck problem are discussed. Following that, a lower bound of competitive ratio for the on-line k-truck problem is given. Based on the Position Maintaining Strategy (PMS), we get some new results which are slightly better than those of [1] for general cases. We also use the Partial-Greedy Algorithm (PG) to solve this problem on a special line. Finally, we extend the concepts of the on-line k-truck problem to obtain a new variant: Deeper On-line k-Truck Problem (DTP).

AB - In this paper, some results concerning the k-truck problem are produced. First, the algorithms and their complexity concerning the off-line k-truck problem are discussed. Following that, a lower bound of competitive ratio for the on-line k-truck problem is given. Based on the Position Maintaining Strategy (PMS), we get some new results which are slightly better than those of [1] for general cases. We also use the Partial-Greedy Algorithm (PG) to solve this problem on a special line. Finally, we extend the concepts of the on-line k-truck problem to obtain a new variant: Deeper On-line k-Truck Problem (DTP).

UR - http://www.scopus.com/inward/record.url?scp=84949784157&partnerID=8YFLogxK

M3 - Conference article published in proceeding or book

SN - 354043996X

SN - 9783540439967

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 504

EP - 513

BT - Computing and Combinatorics - 8th Annual International Conference, COCOON 2002, Proceedings

PB - Springer Verlag

T2 - 8th Annual International Conference on Computing and Combinatorics, COCOON 2002

Y2 - 15 August 2002 through 17 August 2002

ER -