Optimal backlog in the plane

Details Optimal backlog in the plane Optimal backlog in the plane

2008-04-30

arxiv.org/abs/0804.4819v1

Computer Science

Data Structures and Algorithms

10 pages, 1 figure

Scientific paper

Suppose that a cup is installed at every point of a planar set $P$, and that somebody pours water into the cups. The total rate at which the water flows into the cups is 1. A player moves in the plane with unit speed, emptying the cups. At any time, the player sees how much water there is in every cup. The player has no information on how the water will be poured into the cups in the future; in particular, the pouring may depend on the player's motion. The backlog of the player is the maximum amount of water in any cup at any time, and the player's objective is to minimise the backlog. Let $D$ be the diameter of $P$. If the water is poured at the rate of 1/2 into the cups at the ends of a diameter, the backlog is $\Omega(D)$. We show that there is a strategy for a player that guarantees the backlog of $O(D)$, matching the lower bound up to a multiplicative constant. Note that our guarantee is independent of the number of the cups.

Affiliated with

Also associated with

No associations

Rating

Optimal backlog in the plane does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal backlog in the plane, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal backlog in the plane will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-577973