Abstract
We present a poly-log-competitive deterministic online algorithm for the online transportation problem on hierarchically separated trees when the online algorithm has one extra server per site. Using metric embedding results in the literature, one can then obtain a poly-log-competitive randomized online algorithm for the online transportation on an arbitrary metric space when the online algorithm has one extra server per site.
Supported in part by NSF grants CNS-0325353, CCF-0514058 and IIS-0534531.
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
Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: ACM Symposium on Theory of Computing, pp. 161–168 (1998)
Charikar, M., Chekuri, C., Goel, A., Guha, S., Plotkin, S.: Approximating a finite metric by a small number of tree metrics. In: Symposium on Foundations of Computer Science, p. 379 (1998)
Csaba, B., Pluhar, A.: A randomized algorithm for the on-line weighted bipartite matching problem. Journal of Scheduling (to appear)
Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences Special Issue on STOC 2003 69(3), 485–497 (2004)
Gupta, A., Hajiaghayi, M.T., Räcke, H.: Oblivious network design. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 970–979 (2006)
Kalyanasundaram, B., Pruhs, K.: Online weighted matching. Journal of Algorithms 14(3), 478–488 (1993)
Kalyanasundaram, B., Pruhs, K.: On-line network optimization problems. In: Developments from a June 1996 seminar on Online Algorithms, pp. 268–280. Springer, Heidelberg (1998)
Kalyanasundaram, B., Pruhs, K.R.: The online transportation problem. SIAM Journal of Discrete Mathematics 13(3), 370–383 (2000)
Kennington, J.L., Helgason, R.V.: Algorithms for Network Programming. John Wiley & Sons, Inc., New York, NY, USA (1980)
Khuller, S., Mitchell, S.G., Vazirani, V.V.: On-line algorithms for weighted bipartite matching and stable marriages. Theoretical Computer Science 127(2), 255–267 (1994)
Lawler, E.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart & Winston, New York (1976)
Meyerson, A., Nanavati, A., Poplawski, L.: Randomized online algorithms for minimum metric bipartite matching. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 954–959 (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chung, C., Pruhs, K., Uthaisombut, P. (2008). The Online Transportation Problem: On the Exponential Boost of One Extra Server. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds) LATIN 2008: Theoretical Informatics. LATIN 2008. Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78773-0_20
Download citation
DOI: https://doi.org/10.1007/978-3-540-78773-0_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78772-3
Online ISBN: 978-3-540-78773-0
eBook Packages: Computer ScienceComputer Science (R0)