On the On-Line Weighted k-Taxi Problem
作者： Weimin Ma , Ke Wang
DOI: 10.1007/978-3-540-74450-4_14
关键词:
摘要: Based on some results of k-server problem and k-taxi problem, the on-line weighted is originally proposed studied by our team. In cost every taxi same distance different whereas that in traditional problem. this paper, formulation presented first. Following that, preliminary which used to get main theorems are given. Thirdly, online algorithms designed address competitive analysis given detail. Furthermore, lower bound ratio for special cases obtained. Finally, conclusions made future research directions pointed out.
springer.com
springerlink.com参考文章(12)
Weimin Ma, Ke Wang, On the On-Line k-Truck Problem with Benefit Maximization Algorithms and Computation. pp. 660- 669 ,(2006) , 10.1007/11940128_66
Chun-lin Xin, Wei-min Ma, Scheduling for on-line taxi problem on a real line and competitive algorithms international conference on machine learning and cybernetics. ,vol. 5, pp. 3078- 3083 ,(2004) , 10.1109/ICMLC.2004.1378561
Elias Koutsoupias, David Scot Taylor, The CNN Problem and Other k-Server Variants symposium on theoretical aspects of computer science. pp. 581- 592 ,(2000) , 10.1007/3-540-46541-3_48
Daniel D. Sleator, Robert E. Tarjan, Amortized efficiency of list update and paging rules Communications of The ACM. ,vol. 28, pp. 202- 208 ,(1985) , 10.1145/2786.2793
Leah Epstein, Csanád Imreh, Rob van Stee, More on weighted servers or FIFO is better than LRU Theoretical Computer Science. ,vol. 306, pp. 305- 317 ,(2003) , 10.1016/S0304-3975(03)00287-1
Marek Chrobak, Jiřı́ Sgall, The weighted 2-server problem Theoretical Computer Science. ,vol. 324, pp. 289- 312 ,(2004) , 10.1016/J.TCS.2004.05.020
Mark S Manasse, Lyle A McGeoch, Daniel D Sleator, Competitive algorithms for server problems Journal of Algorithms. ,vol. 11, pp. 208- 230 ,(1990) , 10.1016/0196-6774(90)90003-W
Amos Fiat, Moty Ricklin, Competitive algorithms for the weighted server problem Theoretical Computer Science. ,vol. 130, pp. 85- 99 ,(1994) , 10.1016/0304-3975(94)90154-6
WEIMIN MA, YINFENG XU, JANE YOU, JAMES LIU, KANLIANG WANG, On the k-truck scheduling problem International Journal of Foundations of Computer Science. ,vol. 15, pp. 127- 141 ,(2004) , 10.1142/S0129054104002340
Wei-min Ma, Ke Wang, On-Line Taxi Problem on the Benefit-Cost Graphs international conference on machine learning and cybernetics. pp. 900- 905 ,(2006) , 10.1109/ICMLC.2006.258494