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

Abstract

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
Pages504-513
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)
Volume2387
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference8th Annual International Conference on Computing and Combinatorics, COCOON 2002
CountrySingapore
CitySingapore
Period15/08/0217/08/02

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this