Abstract
Based on some results of the on-line k-truck problem with cost minimization, a realistic model of the on-line k-truck problem with benefit maximization is proposed. In the model, the object of optimization is how to design on-line algorithms to maximize the benefit of all trucks’ moving. In this paper, after the model’s establishment, several on-line algorithms, e.g., Position Maintaining Strategy, Partial Greedy Algorithm, are employed to address the problem. The analyses concerning the competitive ratios of the algorithms are given in detail. Furthermore, the lower bound of competitive ratio is discussed.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communication of the ACM 28, 202–208 (1985)
Goldberg, A.V., Hartline, J.D.: Competitiveness via Consensus. In: 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003) (2003)
Hartline, J.D., Goldberg, A.V.: Envy-Free Auctions for Digital Goods. In: Proc. 4th ACM Conf. on Electronic Commerce (2003)
Bartal, Y., Chin, F.Y.L., Chrobak, M., Fung, S.P.Y., Jawor, W., Lavi, R., Sgall, J., Tichy, T.: Online competitive algorithms for maximizing weighted throughput of unit jobs. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 187–198. Springer, Heidelberg (2004)
El-Yaniv, R., Fiat, A., Karp, R.M., et al.: Competitive analysis of financial games. In: Proc. 33rd Annual Symposium on Foundations of Computer Science, pp. 327–333 (1992)
El-Yaniv, R., Fiat, A., Karp, R.M., et al.: Optimal search and one-way trading online algorithms. Algorithmica 30, 101–139 (2001)
Koutsoupias, E., Papadimitriou, C.: On the k-server conjecture. Journal of ACM 42(5), 971–983 (1995)
Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. Journal of Algorithms (11), 208–230 (1990)
Ma, W.M., Xu, Y.F., Wang, K.L.: On-line k-truck problem and its competitive algorithm. Journal of Global Optimization 21(1), 15–25 (2001)
Ma, W.M., Xu, Y.F., You, J., Liu, J., Wang, K.L.: On the k-truck scheduling problem. International Journal of Foundations of Computer Science 15(1), 127–141 (2004)
Ma, W.M., Wang, K.: On-line taxi problem on the benefit-cost graphs. In: Airoldi, E., Blei, D.M., Fienberg, S.E., Goldenberg, A., Xing, E.P., Zheng, A.X. (eds.) ICML 2006. LNCS, vol. 4503, pp. 900–905. Springer, Heidelberg (2007)
Xu, Y.F., Wang, K.L., Zhu, B.: On the k-taxi problem. Information 2(4) (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ma, W., Wang, K. (2006). On the On-Line k-Truck Problem with Benefit Maximization. In: Asano, T. (eds) Algorithms and Computation. ISAAC 2006. Lecture Notes in Computer Science, vol 4288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11940128_66
Download citation
DOI: https://doi.org/10.1007/11940128_66
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49694-6
Online ISBN: 978-3-540-49696-0
eBook Packages: Computer ScienceComputer Science (R0)