New results on the k-truck problem

Weimin Ma, Yinfeng Xu, Jia You, James Liu, Kanliang Wang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review


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).
Original languageEnglish
Title of host publicationComputing and Combinatorics - 8th Annual International Conference, COCOON 2002, Proceedings
PublisherSpringer Verlag
Number of pages10
ISBN (Print)354043996X, 9783540439967
Publication statusPublished - 1 Jan 2002
Event8th Annual International Conference on Computing and Combinatorics, COCOON 2002 - Singapore, Singapore
Duration: 15 Aug 200217 Aug 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th Annual International Conference on Computing and Combinatorics, COCOON 2002

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'New results on the k-truck problem'. Together they form a unique fingerprint.

Cite this