A polylogarithmic-competitive algorithm for the k-server problem

Autor: Bansal, N., Buchbinder, N., Madry, A., Naor, J., Ostrovsky, R.

Publikováno v: FOCS
Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011, Palm Springs CA, USA, October 22-25, 2011), 267-276
STARTPAGE=267;ENDPAGE=276;TITLE=Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011, Palm Springs CA, USA, October 22-25, 2011)
Journal of the ACM, 62(5):40, 1-49. Association for Computing Machinery, Inc

We give the first polylogarithmic-competitive randomized online algorithm for the k -server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of Õ(log 3 n log 2 k ) for any metric space on n point

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c47eff76fe7f5e3171cad70710cbe83d
https://doi.org/10.1145/2783434

Metrical task systems and the k-server problem on HSTs

Autor: Bansal, N., Buchbinder, N., Naor, J., Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G.

Publikováno v: Automata, Languages and Programming ISBN: 9783642141645
ICALP (1)
Automata, Languages and Programming (37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010. Proceedings, Part I), 287-298
STARTPAGE=287;ENDPAGE=298;TITLE=Automata, Languages and Programming (37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010. Proceedings, Part I)

We consider the randomized k-server problem, and give improved results for various metric spaces. In particular, we extend a recent result of Coté et al [15] for well-separated binary Hierarchically Separated Trees (HSTs) to well-separated d-ary HST

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::aa98ae4cc2f8bcf778bb53ca31004c6a
https://doi.org/10.1007/978-3-642-14165-2_25

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Min-max graph partitioning and small set expansion

Autor: Bansal, N., Feige, U., Krauthgamer, R., Makarychev, K., Magarajan, V., Naor, J., Schwartz, R., Ostrovsky, R.

Publikováno v: SIAM Journal on Computing, 43(2), 872-904. Society for Industrial and Applied Mathematics (SIAM)
Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011, Palm Springs CA, USA, October 22-25, 2011), 17-26
STARTPAGE=17;ENDPAGE=26;TITLE=Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011, Palm Springs CA, USA, October 22-25, 2011)
FOCS

We study graph partitioning problems from a min-max perspective, in which an input graph on n vertices should be partitioned into k parts, and the objective is to minimize the maximum number of edges leaving a single part. The two main versions we co

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e3d2881b8ad07db0fa17040f460367c8
https://doi.org/10.1109/focs.2011.79

Towards the randomized k-server conjecture: A primal-dual approach

Autor: Bansal, N., Buchbinder, N., Naor, J., Charikar, M.

Publikováno v: Proceedings 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10, Austin TX, USA, January 17-19, 2010), 40-55
STARTPAGE=40;ENDPAGE=55;TITLE=Proceedings 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10, Austin TX, USA, January 17-19, 2010)

Recently, Coté et al. [10] proposed an approach for solving the k-server problem on Hierchically Separated Trees (HSTs). In particular, they define a problem on a uniform metric, and show that if an algorithm with a certain refined guarantee exists

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=narcis______::7a11650a91b463ddc24e36c439b9da8d
https://research.tue.nl/nl/publications/9616bb81-ad77-4970-a2d4-293f10962062