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

Approximation algorithms for diversified search ranking

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

Publikováno v: Automata, Languages and Programming (37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010. Proceedings, Part II), 273-284
STARTPAGE=273;ENDPAGE=284;TITLE=Automata, Languages and Programming (37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010. Proceedings, Part II)
Automata, Languages and Programming ISBN: 9783642141614
ICALP (2)

A fundamental issue in Web search is ranking search results based on user logs, since different users may have different preferences and intents with regards to a search query. Also, in many search query applications, users tend to look at only the t

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c82e6de50749160cfeaf1c8ffb44001b
https://doi.org/10.1007/978-3-642-14162-1_23

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