intro
In the k-server problem you have k “servers” located in some topological space. You recieve a series of “requests”, which are points in the topological space. You must respond to the request by moving some subset of your servers so that at least one server goes to the request. We will consider this problem in a metric space. You objective is to minimize the total distance travelled by all your servers. More precisely, our objective is to create a strategy that achieves bounded competitive ratio. We consider this problem with k=2 and set on a circle, where distance is measured along the circle.
A lot of obvious strategies that you might try fail to have bounded competitive ratio:
- “double cover” (move both servers closer to the request until one reaches it). This is bad: imagine the requests alternated between poles of the circle, and the servers started at anti-poles.
- “decayed double cover” (move closer server distance \(d\) to the request, and the other server distance \(\frac{d}{2}\) towards the request). Imagine there is a series of requests near one of the servers, and the other server is on the opposite side of the circle. We can make it oscilate and never reach
- “just move the closest one”. The same example as above shows that this is bad.
At this point one might despair of finding any strategy that achieves bounded competitive ratio. But there is this other problem called ski-rental. The idea there is “rent skis until you’ve payed the cost of skis and then buy skis.” This is two competitive, because an adversary always breaks your legs after you buy skis.
Anyways, what does that have to do with this problem?
try1
I propose the following strategy
Proposition. Name the servers server \(1\) and server \(2\). Let \(w_i\) denote the distance travelled so far by server \(i\) and let \(d_i\) denote the distance from server \(i\) to the request.
Then, we send whichever server minimizes \(d_i + w_i\) to cover the request.
TODO: - show that this has bounded competitive ratio - or that it does not
try2
update: I have not been able to analyze the above proposed algorithm yet. However, I have another algorithm that might work, by which I mean get bounded competitive ratio and imply nothing about how good the constants are going to be. Actually, in writing this disclaimer, I am preparing you for some terrible constants.
Ok here’s a rough sketch of a picture of a picture of the idea:Proposition. Think of the servers as really good friends. They want to be close to one another. Sometimes they have to work in separate places. But when they do, they save up all there money and teleport back together as soon as they’ve saved up enough money.
Slightly more formally, here is how the friend’s work:
if they are close, say within \(\frac{1}{8}\) of one-another , the world looks like a line to them, just like how earth looks flat if you’re looking locally.
So, when they are close they double-cover. Like actual double cover, i.e., if request is on an endpoint only send one of them.
All is blissful when they are close. That is, we are 2 competitive on such a sequence. Ok, I mean this is assuming that we started in the same place as opt, which might be a bit tricky, but let’s ignore that for a moment.
But sometimes one or the other needs to travel far away. But once it happens that \(|x-y| > \frac{1}{8}\), then they keep track of how much they move. Once they’ve accumulated \(1\) movement betweeen them, or something, they teleport back together.
When they’re far apart from each other they just handle requests by sending the closer of the two of them.
Oh, and we can exit a far apart phase early if they end up to land close to one another by chance sometime.
But basically once they’ve travelled distance \(1\) appart (or maybe this should be once one of them has travelled \(+1\) more than the other, but I think it might not matter), they teleport back together and hopefully start another small world phase.
But the “return” teleportation is fine because we ammortize it against all the time they spent apppart.
so, this is not actually a formal proof yet. but it’s a fun story at least.
try3
ok, third try is the charm. albiet a somewhat gross charm.
Proposition. We define some terminology
- Single Small world sequence: a series of requests all within a single interval of length \(\frac{1}{32}\), starting from the servers being at a single location
- Two Small world sequence: a series of requests fitting within two intervals of size \(\frac{1}{32}\) arround the two starting locations which are spaced out by at least \(\frac{1}{32}\)
- Break One: you were living in a single small world and then a request came far away.
- Break Two: you were living in two small worlds and a request came outside of both of them
Strategy: - when in single small world double cover - when in two small worlds each person deals with their own world, but they save up money together to teleport back together - when a break one happens one dude teleports to the request and the other dude is allowed to go to an arbitrary location within the small world - when a break two happens they both are allowed to go to arbirarty locations (namely the next two requests) Note that actually break one and break two are the same thing. ok. shrug.
Anyways here’s the story - single small world: double cover is nice - “breaks”: we can do whatever because OPT had to pay as well - two small worlds - Case 1: OPT is also living in two small worlds. Then we are matching opt until we save up enough to teleport back together. and the matching opt stuff pays for the teleport back together - Case 2: OPT actually is living in a single smalll world. i.e., it teleported out of one of the small worlds. But that teleport pays for our teleport and the work we do when in two small worlds
Overall, this is certainly \(1024\) competitive.