In this talk I introduced the three problems mentioned in the title and the connection between them. I mentioned a few lower / upper bounds. I later introduced the problem I am working on - metrical service systems with k servers. I presented a proof of a lower bound on the competitive ratio, which holds for any metric space with sufficiently many points. For the case when the underlying metric space is uniform (and the problem is in some sense a variant of the caching problem), I presented a deterministic algorithm (proposed by Prof. Sundar) with competitive ratio k times the lower bound. Improving on this upper bound is one of the problems I am stuck with.
The proof of the competitive ratio used a result called the skew Bollobás theorem, which I would like to talk on some time. The proof uses what is called the "wedge product" of vectors, in addition to elementary linear algebra. In another talk, I would like to present a randomized algorithm for MSS with k servers on uniform metric space, as well as a few online traversal problem, and their "equivalence" with one another and with MSS.
Ashish Chiplunkar
No comments:
Post a Comment