New results on the k-truck problem

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

New results on the k-truck problem

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

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-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 language	English
Title of host publication	Computing and Combinatorics - 8th Annual International Conference, COCOON 2002, Proceedings
Publisher	Springer Verlag
Pages	504-513
Number of pages	10
ISBN (Print)	354043996X, 9783540439967
Publication status	Published - 1 Jan 2002
Event	8th Annual International Conference on Computing and Combinatorics, COCOON 2002 - Singapore, Singapore Duration: 15 Aug 2002 → 17 Aug 2002

Publication series

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

Conference

Conference	8th Annual International Conference on Computing and Combinatorics, COCOON 2002
Country/Territory	Singapore
City	Singapore
Period	15/08/02 → 17/08/02

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Cite this

@inproceedings{f076fa2ffd344ef2ac05a913e5fb4476,

title = "New results on the k-truck problem",

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).",

author = "Weimin Ma and Yinfeng Xu and Jia You and James Liu and Kanliang Wang",

year = "2002",

month = jan,

day = "1",

language = "English",

isbn = "354043996X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "504--513",

booktitle = "Computing and Combinatorics - 8th Annual International Conference, COCOON 2002, Proceedings",

address = "Germany",

note = "8th Annual International Conference on Computing and Combinatorics, COCOON 2002 ; Conference date: 15-08-2002 Through 17-08-2002",

}

Ma, W, Xu, Y, You, J, Liu, J & Wang, K 2002, New results on the k-truck problem. in Computing and Combinatorics - 8th Annual International Conference, COCOON 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2387, Springer Verlag, pp. 504-513, 8th Annual International Conference on Computing and Combinatorics, COCOON 2002, Singapore, Singapore, 15/08/02.

New results on the k-truck problem. / Ma, Weimin; Xu, Yinfeng; You, Jia et al.
Computing and Combinatorics - 8th Annual International Conference, COCOON 2002, Proceedings. Springer Verlag, 2002. p. 504-513 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2387).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

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 -

New results on the k-truck problem

Abstract

Publication series

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this