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  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).
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||8th Annual International Conference on Computing and Combinatorics, COCOON 2002|
|Period||15/08/02 → 17/08/02|
- Theoretical Computer Science
- Computer Science(all)