{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T17:08:18Z","timestamp":1649178498031},"reference-count":16,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2004,2]]},"abstract":"<jats:p> In this paper, some results concerning the k-truck problem are produced. Firstly, the algorithms and their complexity concerning the off-line k-truck problem are discussed. Following that, a lower bound of competitive ratio (1+\u03b8)\u00b7k\/(\u03b8\u00b7k+2) for the on-line k-truck problem is given, where \u03b8 is the ratio of cost of the loaded truck and the empty truck on the same distance, and a relevant lower bound for the on-line k-taxi problem followed naturally. Thirdly, based on the Position Maintaining Strategy (PMS), some new results which are slightly better than those of [11] for general cases are obtained. For example, a c-competitive or (c\/\u03b8+1\/\u03b8+1)-competitive algorithm for the on-line k-truck problem depending on the value of \u03b8, where c is the competitive ratio of some algorithm to a relevant k-server problem, is developed. The Partial-Greedy Algorithm (PG) is used as well to solve this problem on a line with n nodes and is proved to be a (1+(n-k)\/\u03b8)-competitive algorithm for this case. Finally, the concepts of the on-line k-truck problem are extended to obtain a new variant: Deeper On-line k-Truck Problem (DTP). We claim that results of PMS for the STP (Standard Truck Problem) hold for the DTP. <\/jats:p>","DOI":"10.1142\/s0129054104002340","type":"journal-article","created":{"date-parts":[[2004,3,18]],"date-time":"2004-03-18T12:03:47Z","timestamp":1079611427000},"page":"127-141","source":"Crossref","is-referenced-by-count":9,"title":["ON THE k-TRUCK SCHEDULING PROBLEM"],"prefix":"10.1142","volume":"15","author":[{"given":"WEIMIN","family":"MA","sequence":"first","affiliation":[{"name":"School of Management,  Xian Jiaotong University, Xian, Shaanxi, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YINFENG","family":"XU","sequence":"additional","affiliation":[{"name":"School of Management,  Xian Jiaotong University, Xian, Shaanxi, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JANE","family":"YOU","sequence":"additional","affiliation":[{"name":"Department of Computing,  Hong Kong Polytechnic University, Kowloon, Hong Kong, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JAMES","family":"LIU","sequence":"additional","affiliation":[{"name":"Department of Computing,  Hong Kong Polytechnic University, Kowloon, Hong Kong, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KANLIANG","family":"WANG","sequence":"additional","affiliation":[{"name":"School of Management,  Xian Jiaotong University, Xian, Shaanxi, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","volume":"31","author":"Albers S.","journal-title":"ACM Computing Surveys"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146588"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1137\/0404017"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1137\/0220008"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029561"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762111"},{"key":"rf9","first-page":"143","volume":"33","author":"Kierstead H. A.","journal-title":"Congressus Numerantium"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1145\/210118.210128"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1023\/A:1017982528216"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90003-W"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.2307\/2319522"},{"key":"rf17","volume":"2","author":"Xu Y. F.","journal-title":"Information"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322187"},{"key":"rf19","first-page":"47","volume":"31","author":"Ying B. A.","journal-title":"Navigation Computing Technology"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054104002340","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:25:51Z","timestamp":1565191551000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054104002340"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,2]]},"references-count":16,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2004,2]]}},"alternative-id":["10.1142\/S0129054104002340"],"URL":"https:\/\/doi.org\/10.1142\/s0129054104002340","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,2]]}}}