The problem of centrally assigning drivers to parking spots to minimize time and fuel usage may be reasonably modeled by the online metric matching problem. The setting for this problem is a collection of servers S = {s 1 , . . . , s n } (the parking spots) located at various locations in a metric space. In the case that the metric space is a line, we name the servers so that s 1 ≤ s 2 . . . ≤ s n . Over time a sequence R = {r 1 , . . . , r n } of requests (the cars) arrive at various locations in the metric space. Upon the arrival of each request (car) r i , the online algorithm must irrevocably be assigned r i to an available server (parking spot) s σ(i) , which results in s σ(i) being unavailable going forward. Conceptually think of the request (car) r i moving to server (parking spot) s σ(i) . Thus the cost incurred by such an assignment is the distance d(s σ(i) , r i ) between the location of s σ(i) and the location where r i arrived. The objective is to minimize the total cost of matching the requests (cars) to the servers (parking spots).

However, in order to be implementable within the context of SFpark, online algorithms must be posted-price algorithms. In this setting, posted-price means that before each car arrives, the algorithm sets a price on each available parking spot without knowing the next car's arrival location. We assume each car is driven by a selfish agent who moves to the available parking spot that minimizes the sum of the price of that parking spot and the distance to that parking spot. The objective remains to minimize the aggregate distance traveled by the cars. It is important to note that conceptually the objective of the parking pricing agency is minimizing social cost (or equivalently maximizing social good), not maximizing revenue.

Research into posted-price algorithms for online metrical matching was initiated in [12], as part of a line of research to study the use of posted-price algorithms to minimize social cost in online optimization problems. As a postedprice algorithm is a valid online algorithm, one cannot expect to obtain a better competitive ratio for posted-price algorithms than what is achievable by online algorithms. So this research line has primarily focused on problems where the optimal competitive ratio achievable by an online algorithm is (perhaps approximately) known, and seeks to determine whether a similar competitive ratio can be (again perhaps approximately) achieved by a posted-price algorithm. The higher-level goal is to determine the increase in social cost that is necessitated by the restriction that an algorithm has to use posted prices to incentivize selfish agents, instead of being able to mandate agent behavior.

Essentially all results in the posted-price online algorithms literature use one of two algorithmic design techniques. The simpler algorithmic design paradigm is called mimicry. A posted-price algorithm A mimics an online algorithm B if the probability that B will take a particular action is equal to the probability that a self-interested agent will choose this same action when the prices of actions are set using A. However, many online algorithms are not mimickable. So another algorithmic design paradigm, called monotonization, first seeks to identify a sufficient property for an online algorithm to be mimickable, and then seeks to design an online algorithm with this property. In all the examples in the literature, the identified property involves some sort of monotonicity in the behavior of the algorithm. In particular, for online metric matching on a tree metric (which includes a line as a special case), an online algorithm A is mimickable if and only if it is monotone in the sense that as the request location moves closer to the location of an available server the probability that the request is matched to that server cannot decrease [9].

There are three online algorithms for online metric matching on a line that interest us here:

-The Robust Matching (RM) algorithm is a deterministic primal-dual algorithm that is Θ(log n)-competitive [22]. The Robust Matching algorithm is not mimickable [8], and intuitively seems far from being mimickable. -The Harmonic (H) algorithm is a randomized algorithm that is Θ(log Δ)competitive, where Δ is the ratio of the distance between the furthest pair of servers and the distance between the closest pair of servers [15]. The Harmonic algorithm chooses between the first available server to the left of the request and the first available server to the right of the request with probability inversely proportional to the distance from the request to these servers. [12] showed that the Harmonic algorithm is mimickable, thus obtaining an O(log Δ)-competitive posted-price algorithm. -The Doubled Harmonic (DH) algorithm is a randomized algorithm that is O(log n)-competitive. Doubled Harmonic combines a variation of Harmonic that uses an estimation Z of the optimal cost (between the requests and the servers), with a standard guess-and-double technique for maintaining a good estimate of the current optimal cost to date [15]. We show in Appendix B that Doubled Harmonic is not mimickable.

Thus the specific research question that we address is whether we can design a monotone variation of Doubled Harmonic that is O(log n)-competitive, thus leading to an O(log n)-competitive posted-price algorithm. But, even though it is the title of the paper, obtaining a better competitive ratio is only a secondary motivation for this research. Our primary motivation is to determine whether in this setting we can implement guess-and-double monotonically, with the hope that this will provide insights into designing posted-price algorithms in other settings where the standard online algorithms use the ubiquitous guess-and-double technique. To understand why answering this research question isn't completely straightforward, we need to first understand the Doubled Harmonic algorithm.

Firstly, for ease of presentation, we will make some simplifying assumptions, namely:

-No pair of servers is closer than 1 unit of distance from each other. We show that this is without loss of generality in Appendix A.1. -All requests arrive at the location of some server. We show that this is without loss of generality in Appendix A.2.

Intuitively Doubled Harmonic modifies Harmonic in following waysfoot_0 . Firstly, if the distance between consecutive servers is small (less than Z/n 2 ), where Z is the estimate of optimal maintained by the algorithm, then this distance is artificially inflated (to Z/n 2 ). Secondly, if the actual optimal cost between the requests and servers becomes at least the estimate Z, then the estimate Z is increased geometrically until it exceeds the current optimal cost, and the algorithm conceptually reruns itself on all the requests to date with this new estimate to compute which servers it would ideally like to be available now. The algorithm then continues forward imagining these servers are available, and then correcting to the actually available servers using some optimal matching between the imaginary available servers and the actually available servers. Unfortunately the full algorithm, with corner cases, is a bit more complicated.

Definition 1. We define the pseudo-distance pd (s i , s i+1 ) between two adjacent servers s i and s i+1 to be

and s i+1s i otherwise; here Z will be a parameter in the algorithms. We then define the pseudo-distance between two arbitrary servers s i and s j , where i < j to be j-1 h=i pd (s h , s h+1 ).

Until a request arrives at a location where there is not an available server, the request is assigned to the available server where it arrives. When the first request r t arrives at a location where there isn't an available server, the Doubled Harmonic algorithm maintains the following invariants:

-An estimate Z = 10 j , for some integer j, such that optimal cost to date is at least Z/10 and is strictly less than Z. -A set of imaginary servers S ι = {s ι(1) , . . . s ι(k) } that in some sense the algorithm imagines are available (but which may or may not actually be available). S ι is initialized to S -{s σ(1) , . . . , s σ(t-1) }. -The set S ρ = {s ρ(1) , . . . s ρ(k) } of servers that are really available.

-An arbitrary optimal matching M between S ι and S ρ .

Then it responds to the arrival of a request r t in the following way:

-If r t is triggering, meaning that it causes the optimal cost to date to be at least Z, then the estimate Z is set to 10 j where j is the minimum integer that will reestablish the invariant on Z, and the algorithm then performs what we call an adjustment operation (which we define below) up through request r t-1 . -If there is an imaginary server s ι(i) at the location of r t then no action is taken (later we will think of this as an imaginary move of length 0). -If there is no imaginary server to the left of r t then it moves to the first imaginary server to its right. This is called an imaginary move.

-Else if there is no imaginary server to the right of r t then it moves to the first imaginary server to its left. This is called an imaginary move. -Else let s ι(h) and s ι(h+1) be the first imaginary servers to the left and right of r t , respectively. Then r t moves to s ι(h) with probability

and r t moves to s ι(h+1) with probability

So the algorithm chooses between the imaginary server to the left and the imaginary server to the right with probability inversely proportional to the pseudo-distance. Let us call this movement imaginary movement.

-After the imaginary movement of the request to a server in s ι(j) ∈ S ι , the request continues moving to the server in s ρ(h) ∈ S ρ that s ι(j) is matched to in M , which we call a corrective move, and s ι(j) is removed from S ι .

This algorithm takes as input a request r t . The algorithm simulates Doubled Harmonic on all requests up to r t , sets S ι to be the servers that would be available at the end of this simulation, and recomputes an optimal matching M .

There are two reasons why modifying Doubled Harmonic to be monotone isn't straightforward (and presumably why this wasn't done in [12]):

1. The first is that the behavior of the algorithm is quite different depending on whether the new request is triggering or not, which is challenging to implement with prices because the prices have to be set before the location of the request is known. 2. The correction moves used by Doubled Harmonic are intuitively not coordinated with the imaginary moves.

Our main contribution is an algorithm that we call Modified Doubled Harmonic (MDH) that circumvents these issues by modifying Doubled Harmonic in the following way:

1. Triggering requests r t are just assigned as though they had appeared at a location x near r t where r t would not have been triggering had it arrived at location x. Intuitively because triggering requests are rare, it's not particularly critical that they be handled cheaply. 2. During the correction step the request moves in same direction as it would in Doubled Harmonic, but stops at the first available server. Note that this correction step cannot be implemented by any fixed matching, as Doubled Harmonic does.

One big hurdle in naturally extending poly-log competitiveness results on posted-price algorithms for online metric matching on a spider metric [9,10] to tree metrics is the seeming need to be able to implement guess-and-double in a monotonic way on a tree, which was the main motivation for considering how to accomplish this on a line [8]. So our takeaway is that this result suggests trying to design the correction step for a tree to be as flexible as possible, so as to make it as easy as possible to monotonically blend with the imaginary movement.

Due to space limitations some proofs have been moved to appendix.

Online metric matching was first studied in [17,18], and each showed independently that (2n-1)-competitive is the optimal competitive ratio for deterministic algorithms in a general metric space. The best known competitive ratio for a randomized algorithm against an oblivious adversary is O log 2 n [7,20], and the best known lower bound is Ω(log n).

In this paper, we focus on matching on the line, which is perhaps the most interesting case. [4] gave the first deterministic, o(n)-competitive algorithm for this problem. [19] showed that the Generalized Work Function algorithm is Ω(log n) and O(n) competitive. [21] showed that no randomized algorithm can achieve a competitive ratio of o √ log n for online matching on the line. [14] shows how to set prices to mimic the O(1)-competitive algorithm Slow-Fit from [5,6] for the problem of minimizing makespan on related machines. Monotonization is used in [16] to obtain an O(1)-competitive posted-price algorithm for minimizing maximum flow time on related machines.

We explain the Modified Doubled Harmonic algorithm mainly in terms of how it differs from Doubled Harmonic. Modified Doubled Harmonic makes the same initial assumptions about the instance, and maintains the same invariants, as does Doubled Harmonic. Intuitively Modified Doubled Harmonic modifies Doubled Harmonic in the following ways. Firstly, it handles a triggering request (by pretending it arrived at a nearby point where the request wouldn't have been triggering if it arrived there) before doing the double step of guess-and-double. Secondly, during the correction step the request moves in same direction as it would in Doubled Harmonic, but stops at the first available server. Unfortunately the details of both of these two modifications are a bit complicated.

Note that the optimal matching M between S ι and S ρ partitions the real line into subintervals of three different types:

Left Islands are maximal subintervals that contain points x where an s ι(j) ∈ S ι to the right of x is matched to a s ρ(h) ∈ S ρ to the left of x in M .

Right Islands are maximal subintervals that contain points x where an s ι(j) ∈ S ι to the left of x is matched to a s ρ(h) ∈ S ρ to the right of x in M .

Stationary Islands are maximal subintervals that are disjoint from left and right islands.

Note that this partitioning will be the same for all choices of M [22].

The algorithm behaves the same way as Doubled Harmonic up until the first request that arrives at the location of an unavailable server. The algorithm responds to the arrival of a subsequent request r t in the following manner:

1. If r t appears at the location of a available server s ρ(j) , then it is assigned to s ρ(j) . 2. Else if r t appears to the left of the leftmost available server s ρ (1) , then it is assigned to s ρ(1) .

server to its right. (c) Else let s ι(h) and s ι(h+1) be the first imaginary servers to the left and right of r t , respectively. Then r t moves to the first available server to its left with probability

and r t moves to the first available server to its right with probability

So the algorithm chooses between the imaginary server to the left and the imaginary server to the right with probability inversely proportional to the pseudo-distance, and then moves to the nearest available server in that direction. 5. Else (Comment: r t is triggering) (a) Let s ρ(h) and s ρ(h+1) be the first available servers to the left and right of r t , respectively. (b) Let y ℓ be defined in the following way: If one moves from r t to the left, let y ℓ be the first point x that one comes to where either r t would not have been triggering if it had arrived at x, or x is the location of s ρ(h) . (c) Let y r be defined in the following way: If one moves from r t to the right, let y r be the first point x that one comes to where either r t would not have been triggering if it had arrived at x, or x is the location of s ρ(h+1) .

, y r , s ρ(h+1) ) < 1 2 then mimic the assignment of a request appearing at y r . (f ) Else if R(s ρ(h) , y ℓ , s ρ(h+1) ) > 1 2 then mimic the assignment of a request appearing at y ℓ . (g) Else if r t < m then mimic the assignment of a request appearing at y ℓ . (h) Else r t ≥ m, and mimic the assignment of a request appearing at y r . 6. If r t was triggering (this could happen in Cases 1, 2, 3, or 5), the algorithm updates the estimate Z and calls the adjustment operation up through request r t (note the adjustment operation was defined when we defined Doubled Harmonic).

To show Modified Doubled Harmonic is well-defined, we make the following observations. Proof. The first two observations follow directly from the definitions of Left Island and Right Island. The third observation follows from the fact that r t has available servers on each side, and so it must have imaginary servers on each side.

Note that Modified Doubled Harmonic is a neighbor algorithm, that is it always assigns requests to a neighboring server. In Lemma 1 we show that if a neighbor algorithm is monotone on intervals between adjacent available servers s ρ(i) , s ρ(i+1) then it is monotone. In Lemma 2 we analyze the probability of a non-triggering request in s ρ(i) , s ρ(i+1) being assigned to s ρ(i+1) . In Lemma 3 we analyze the probability of a triggering request in s ρ(i) , s ρ(i+1) being assigned to s ρ(i+1) . Then we conclude in Theorem 1 that Modified Doubled Harmonic is monotone on each interval s ρ(i) , s ρ(i+1) .

Let r t → s ρ(j) denote the event that request r t is matched to s ρ(j) . We will use the notation r t = x as shorthand for r t arrived at location x. We say a point x on the line is a trigger point if a request arriving at location x would be a triggering request, and otherwise we say x is a non-trigger point.

Proof. Suppose for all intervals of adjacent available servers

] and A has an available server at s ρ(j+1) . We want to show the following monotonicity condition holds:

We proceed by simple casework. If u = v, then we have equality; and if

Otherwise, if there does not exist an available server to the left of u, then Pr[r t → s ρ(j+1) | r t = v] = 1. Thus, it remains to consider the case where u, v ∈ s ρ(j) , s ρ(j+1) for adjacent available servers at s ρ(j) , s ρ(j+1) . We know Pr r t → s ρ(j+1) | r t = x is non-decreasing across this interval, and so we must have Pr

Thus in all cases, the monotonicity condition holds. If instead we pick u, v, s ρ(j+1) ∈ R 1 arbitrary with v ∈ [s ρ(j+1) , u], the same reasoning holds. Thus the described condition implies A is monotone, and so it is equivalent to monotonicity for neighbor algorithms.

---→ s ρ(j) denote the event that request r t is matched to available server s ρ(j) using Modified Doubled Harmonic. We now fix an arbitrary interval of adjacent available servers s ρ(i) , s ρ(i+1) . Proof. Note that the interval s ρ(i) , s ρ(i+1) can be expressed as the union of a left island, a stationary island, and a right island (any two of which could possibly be empty). Since [22] guarantees they must appear in this order, the fact that MDH assigns a request r t in a stationary island to s ρ(i+1) with probability inversely proportional to its pseudodistance from s ρ(i+1) yields the result.

containing only trigger points be arbitrary. Note that the only information used to make the assignments of triggering requests are the adjacent non-trigger points (or endpoints of the interval) and the arrival location of the triggering requests relative to the midpoint. Since (x L , x R ) contains no non-trigger points and is entirely contained on one side of m, all of this information is identical. Thus, all requests in (x L , x R ) have the same probability of being assigned to s ρ(i+1) .

Proof. The non-trigger points in s ρ(i) , s ρ(i+1) , along with m, partition the interval into subintervals for which Pr r t MDH ---→ s ρ(i+1) | r t = x is constant via Lemma 3. Further, Lemma 2 shows that Pr r t MDH ---→ s ρ(i+1) | r t = x is nondecreasing across non-trigger points, and Case 5 of Definition 4 ensures that the probability of assigning a triggering request to s ρ(i+1) is sandwiched between the probability of assigning its neighboring non-trigger points to s ρ(i+1) . So, Lemma 1 implies that MDH is monotone.

In this section we prove Theorem 2, which states that Modified Doubled Harmonic is O(log n)-competitive.

We first break the execution of Modified Doubled Harmonic into phases, where each phase terminates with a triggering request. We show in Lemma 4 that the aggregate cost of the nontriggering requests during a phase is at most O(log n) times the current estimate of the optimal cost plus the imaginary cost that Doubled Harmonic would have incurred during that phase. We accomplish this by showing that for each nontriggering request, the cost of the optimal matching between the imaginary and available servers decreases by at least the amount that the cost for Modified Doubled Harmonic exceeds the imaginary cost that Doubled Harmonic would have incurred on that request. In Lemma 5 we bound the cost to Modified Doubled Harmonic for a triggering request by twice the greedy cost (which is can be seen to be O(log n) times OPT via the traingle inequality) and the cost to Modified Doubled Harmonic if the request had arrived at a nearby non-trigger point. Once we have established Lemma 4 and Lemma 5, the bounding of Modified Doubled Harmonic's cost proceeds as in [15]. Details can be found in the Appendix.

We first need some definitions. Let S ι (t) be the set of imaginary servers before the arrival of r t , and let S ρ (t) be the set of available servers before the arrival of r t . Let D (S ι (t), S ρ (t)) be the optimal cost of matching S ι (t) and S ρ (t). Let s σ(t) be the available server that Modified Doubled Harmonic used for request r t . For a nontriggering request r t , if r t appeared in a left island or a right island, let s γ(t) be the imaginary server that would be selected if one selected a neighboring imaginary server to either the left or right of r t with probability inversely proportional to the pseudo-distance. If instead r t appeared in a stationary island, then if one moves from r t in the direction of s σ(t) , let s γ(t) be the first imaginary server one hits. Define a phase as the sequence of requests which appear while MDH has the same estimate Z on the optimal cost. Phases begin with a sequence of nontriggering requests, and terminate with a single triggering request, after which the estimate Z inflates. Lemma 4. Consider an arbitrary phase, and renumber the nontriggering requests in that phase to r 1 , r 2 , . . . , r k . With probability one the expression

is a non-increasing function of t.

Proof. Define g(t) to be the above expression for the chosen phase, and let t ∈ [1, k] be arbitrary. Then we have

where S ρ (t + 1) = S ρ (t) \ {s σ(t) } and S ι (t + 1) = S ι (t) \ {s γ(t) }. Write S ρ (t) = {s ρ(1) , s ρ(2) , . . . , s ρ(ℓ) } and S ι (t) = {s ι(1) , s ι(2) , . . . , s ι(ℓ) } where the servers in each set have been ordered left-to-right. Suppose s σ(t) = s ρ(a) and s γ(t) = s ι(b) . Now, suppose a < b. Then because s ρ(a) < s ρ(b) and MDH is a neighbor algorithm, we must have r t < s ρ(b) . Further, because s ι(a) < s ι(b) and s ι(b) is a neighboring imaginary server to r t , we must have r t > s ι(a) . The final observation is the trickiest to notice: r t ≤ s ρ(a) , meaning that a < b implies MDH cannot assign r t leftwards. We can show this through simple casework on the description of Modified Doubled Harmonic. The only cases where leftward assignment is possible are Case 3, Case 4a, and Case 4c. However, in all of these cases, we must have a ≥ b. Indeed, in Case 3, a = ℓ ≥ b. In Case 4a, r t is in a left island, and so [22] shows r t must have more available servers than imaginary servers on its left, forcing a ≥ b. In Case 4c, r t is in a stationary island, and so [22] shows there must be an equal number of available and imaginary servers to the left of (and including the location of) r t . By definition of s γ(t) when r t is in a stationary island, we must have a = b. Thus given a < b, leftward assignment of r t is not possible, and so r t ≤ s ρ(a) . Finally, we can deduce s ι(a) < r t ≤ s ρ(a) < s ρ(b) . Simple computation yields

The first inequality follows by simple computation and application of the triangle inequality, but for completeness, the proof is given in the Appendix (Lemma 6). If a = b, direct computation gives the same result. If a > b, applying the same reasoning as before gives s ρ(b) < s ρ(a) ≤ r t < s ι(a) , and the same result follows. Thus in all cases, g(t + 1)g(t) ≤ 0 giving g(t + 1) ≤ g(t). Thus g(t) is a non-increasing function of t, completing the proof. Lemma 5. Consider a triggering request r t . Let s j be the available server closest to r t . Let y ℓ and y r be defined as in the Modified Doubled Harmonic algorithm, and let s ℓ and s r be the available servers that Modified Doubled Harmonic would have assigned a request arriving at y ℓ and y r , respectively. Then

Proof (Sketch). For brevity we give the proof sketch, and the full proof is given in the Appendix. We proceed by showing the claim holds in each potential trigger case of Definition 4. In Cases 1, 2, and 3, the claim trivially holds, because r t is assigned greedily to s j . It remains to consider Case 5. Suppose r t appeared in between adjacent available servers s ρ(h) and s ρ(h+1) , and let m be the midpoint of s ρ(h) , s ρ(h+1) .

(a) If R(s ρ(h) , y r , s ρ(h+1) ) < 1 2 , then r t mimics the assignment of a request arriving at y r . Thus

r t mimics the assignment of a request appearing at y ℓ . Thus E d r t , s σ(t) ≤ E [d (y ℓ , s ℓ )]. (c) Else if r t < m, then r t mimics the assignment of a request appearing at y ℓ . Because y ℓ ≤ r t ≤ m and R(s ρ(h) , y ℓ , s ρ(h+1) ) ≤ 1 2 , we have E d r t , s σ(t) ≤ 2 max (E [d (y ℓ , s ℓ )] , d (r t , s j )). (d) Else r t ≥ m, and r t mimics the assignment of a request appearing at y r . Because y r ≥ r t ≥ m and R(s ρ(h) , y r , s ρ

Thus in all cases, the claim holds.

First, note that we may always assume the minimum distance between servers at different locations is 1, which can be easily remedied by a suitable scaling. Thus to resolve the assumption that the minimum distance between adjacent servers is 1, the important piece to resolve is that no two servers exist at the same location.

Suppose we have a monotone neighbor algorithm A which is α-competitive under the assumptions that all servers exist at different locations, and requests appear at server locations. We will construct a monotone neighbor algorithm B which is 2α-competitive and removes the first assumption.

Again we may assume the instance given to B has minimum distance 1 between adjacent servers at different locations, which can be easily remedied by a suitable scaling. We do this primarily for ease of analysis. Let = 1 5n . On the instance given to B, construct an instance for A by first placing one server per server location; and then perturbing the extra servers at the same location by at most (so that all servers are now at distinct locations). B then services request r in the following way.

-If r appears at an available server s in the instance of B, place a simulated request r at an available server s in the same " -window" in the instance of A. Then r B -→ s and r A -→ s. -Otherwise, let t be the location of r's appearance. Place a simulated request r at t in the instance of A. Given r A -→ s for an available server s, then r B -→ s.

It is easy to see that B is a monotone neighbor algorithm given A is a monotone neighbor algorithm. It remains to show B is 2α-competitive. Note that each assignment in ON B and OPT B can differ from the corresponding assignment in ON A and OPT A by at most . Thus

If OPT B = 0, then ON B = 0, because all requests appeared at available servers. Otherwise, OPT B > 0, and so some request is forced to match to a server at a different location. Because the minimum distance between adjacent servers (at different locations) is 1, we must have ON B ≥ OPT B ≥ 1. The same property holds for the instance of A (where some request is forced to assign outside of its " -window"), and so ON A ≥ OPT A ≥ 1 -2 ≥ 3 5 . Thus

and so B is 2α-competitive, as desired.

Suppose we have a monotone neighbor algorithm B which is β-competitive under the assumption that requests appear at server locations. We will construct a monotone neighbor algorithm C which is (2β + 1)-competitive and makes no such assumption. Specifically, C services request r in the following way.

-Let t be the server closest to r, regardless of whether t is available or not.

-Place a simulated request r at the location of t in the running instance of B.

-Given r B -→ s for an available server s, then r C -→ s.

Let S = {s 1 , s 2 , . . . , s n } be the set of servers in the instance and R = {r 1 , r 2 , . . . , r n } be the set of requests. Without loss of generality, assume the servers of S and the requests of R have been written, according to their locations, in increasing order of coordinate value. Let t i be the server nearest to r i , regardless of whether it is available or not upon appearance of r i . Then the set T = {t 1 , t 2 , . . . , t n } is written as "ordered" as well.

First, we show C is (2β + 1)-competitive. Suppose B assigns ri to s σ(i) for each i.

, where the structure of OPT B and OPT C is given by [22]. Note OPT C ≥ n i=1 d(r i , t i ) since t i is the nearest server to r i for each request r i . Then we have

as desired. Further, it is easy to see that C is a neighbor algorithm given B is a neighbor algorithm. Lastly, we must show C is monotone. Indeed, the sets of points closest to s i for each server s i partition the real line into disjoint intervals (where all servers at the same location are understood to share the same interval). Any requests appearing within the same interval are treated identically in C. This discretization ensures that because B is monotone and thus satisfies the condition in Lemma 1, C satisfies the same condition, and so it is also monotone.

Consider the following instance.

Suppose that r 1 arrives at s 2 . Then, r 1 DH --→ s 2 . Next, suppose r 2 arrives at s 2 . Then the optimal matching of r 1 and r 2 has cost 4, the estimate Z is set to 10, the set of imaginary servers is set to S ι = {s 1 , s 3 , s 4 }, and the set of available servers is set to S ρ = {s 1 , s 3 , s 4 }. Clearly the optimal matching M between S ι and S ρ just assigns each server to itself. Suppose DH then performs the imaginary move r 2 → s 1 and the subsequent corrective move s 1 → s 1 . This leaves S ι = {s 3 , s 4 } and S ρ = {s 3 , s 4 }. Now, we show that the assignment of r 3 is not monotone.

Suppose that r 3 appears at s 1 . Then, the optimal matching of the requests has cost 7. DH performs the imaginary move r 3 → s 3 and the subsequent corrective move s 3 → s 3 , and so DH assigns r 3 to s 3 with probability 1.

Suppose that r 3 instead appears at s 2 . Now, the optimal matching of the requests has cost 11. The estimate Z is then set to 100, and the adjustment operation is performed. With probability 4 11 , DH simulates assigning r 1 to s 2 and r 2 to s 3 . The imaginary move of r 3 is then to s 1 with probability 27 31 , and the subsequent corrective move assigns r 3 to s 3 . The imaginary move of r 3 to s 4 has probability 4 31 , and the subsequent corrective move assigns r 3 to s 4 . Thus with nonzero probability, DH assigns r 3 to s 4 (and thus NOT to s 3 ) in this case.

Thus the probability that DH assigns r 3 to s 3 is higher for arrival at s 1 (probability 1) than for arrival at s 2 (probability < 1). Further note that this violation of monotonicity is induced by the fact that an adjustment operation will not occur if r 3 arrives at s 1 , but it will occur if r 3 arrives at s 2 . Thus DH is not monotone.

Lemma 6. Let P, Q be two finite sets of points in R 1 with the same number of elements. Suppose P = {p 1 , p 2 , . . . , p m } and Q = {q 1 , q 2 , . . . , q m }, where the points have been written in increasing order of location. Let D(P, Q) be the optimal cost of matching P and Q. Further, let

Proof. We know via [22] that

Then we have

For g > h, the proof follows identically, only with P, Q and g, h switched.

To explicitly prove our cost results, we first introduce many useful definitions.

Let OPT(t) be the optimal cost of matching the first t requests to the servers, and suppose that OPT(n) ∈ 10 ℓ , 10 ℓ+1 . For ease of presentation, suppose that before the estimate Z is instantiated during execution of MDH, it holds a default value of 1. Then the estimate Z runs through Z = 10 ki for 0

Let Z i = 10 ki for each 0 ≤ i ≤ m. We now introduce some definitions which allow us to partition the requests according to Z i . Let -τ i be the maximum index t such that OPT(t) < Z i for each 0 ≤ i ≤ m.

-ρ i be the i'th triggering request, which upon appearance causes OPT(t) to increase from < Z i-1 to ≥ Z i-1 . Equivalently ρ i = r τi-1+1 . -B i be the sequence of requests r t arriving after ρ i and before ρ i+1 .

Let B 0 and B m be the sequence of requests appearing before ρ 1 and after ρ m , respectively. This allows us to decompose the full request sequence as B 0 , ρ 1 , B 1 , ρ 2 , . . . , B m-1 , ρ m , B m . The phase of the algorithm associated with Z i is given by the pair (B i , ρ i+1 ). However, we will no longer use this phase terminology, and rather reference the B i 's and ρ i 's directly. We now introduce some definitions which allow us to partition MDH's assignments and DH's underlying imaginary moves according to Z i . Let -W i = rt∈Bi { r t , s σ(t) } be the set of assigned edges for the requests in B i . -X i = rt∈Bi { r t , s γ(t) } conceptually be the set of chosen imaginary moves for the requests in B i .

Conceptually, X i is a set of possible imaginary moves of Doubled Harmonic. These imaginary moves are relevant for us because we bound the cost of Modified Doubled Harmonic's assignments against the cost of these imaginary moves. We are also interested in how MDH/DH simulates request assignments during an adjustment operation. For this reason, define s μ(i,t) to be the imaginary server chosen for the request r t during the adjustment operation triggered by ρ i . Of course, s μ(i,t) is only defined for t ≤ τ i-1 , because the adjustment operation which occurs after the estimate inflates to Z = Z i only simulates request assignments up to the triggering request ρ i = r τi-1+1 . Now, let s μ(i,t) } be the set of simulated assignments of the requests for the adjustment operation triggered by ρ i .

-e i = { r t , s σ(t ) } be the assigned edge of ρ i . Here t = τ i-1 + 1.

-f i = { r t , s γ(t ) } conceptually be the chosen imaginary move for ρ i . Here t = τ i-1 + 1, and s γ(t ) is a neighboring imaginary server to ρ i chosen with probability inversely proportional to the pseudodistance after the adjustment operation triggered by ρ i is performed. -E i = {e 1 , e 2 , . . . , e i } be the set of assigned edges for the triggering requests up through ρ i .

This allows us to decompose the full assigned edge set W = ( m i=0 W i ) ∪ E m in the order W = W 0 , e 1 , W 1 , e 2 , . . . , W m-1 , e m , W m . We can further decompose the chosen imaginary moves in the order X = X 0 , f 1 , X 1 , f 2 , . . . , X m-1 , f m , X m . Lastly, for an edge set U , let |U | be the sum of the lengths of the edges in U .

Let i ∈ [0, m] be arbitrary. We now pursue the goal of bounding |W i |, the total cost of the non-trigger assignments while Modified Doubled Harmonic has estimate Z = Z i . We start by recalling an important result from [15], which gives a cost bound on the imaginary moves and the simulated assignments from the adjustment operation. Let ti = τ i-1 + 2 be the time of the first request in B i . To bound |W i | -|X i |, we will bound D S ρ ti , S ι ti , which will be sufficient for our purposes upon application of Lemma 4. We do so by constructing a matching M i : S ι ti → S ρ ti whose cost is appropriately bounded.

Proof. [15] Cover the line with {f i } ∪ Y i and i-1 j=0 W j ∪ E i . For all imaginary and available servers at the same location, match them together. Otherwise, for each remaining imaginary server in S ι ti , follow the edges of this covering until an available server in S ρ ti is reached, and match them together. Via the triangle inequality, the induced matching

Proof. ti is the time of the first request in B i , and τ i + 1 is the time of the (i + 1)'st triggering request ρ i+1 . Thus ti ≤ τ i + 1 and so Lemma 4 implies g (τ i + 1) ≤ g ti . Thus

The third inequality follows from the fact that D S ρ ti , S ι ti is the optimal cost of matching S ρ ti and S ι ti . The last inequality follows from Lemma 8. Applying Lemma 7 gives the desired result.

We now prove a sequence of lemmas with the eventual goal of proving Lemma 13. We begin by introducing some basic functions to compute assignment costs. In Lemma 5, we bound the cost to Modified Doubled Harmonic for a triggering request by twice the greedy cost (which is clearly O(log n) times OPT) and the cost to Modified Doubled Harmonic if the request had arrived at a nearby nontrigger point. We bound the greedy cost of ρ i in Lemma 12, and the cost bound on the non-trigger points is a simple corollary from Lemma 9. Combining these results, we prove Lemma 13.

First, we introduce some basic functions for computing assignment costs. The function L h (x) is the linear transformation of s ρ(h) , s ρ(h+1) onto (0, 1) (which maps s ρ(h) to 0 and s ρ(h+1) to 1). The function N (α, γ) = α(1γ) + (1α)γ is a "normalized" assignment cost, where we assume the adjacent available servers exist at 0 and 1. The following lemma makes these ideas rigorous. Lemma 10. Suppose request r t appears in between adjacent available servers s ρ(h) and s ρ(h+1) . Further, suppose r t assigns to s ρ(h) , s ρ(h+1) with probabilities 1p, p. Then the expected cost of r t 's assignment is

Proof. The proof follows directly from simple computation.

The utility of decomposing r t 's assignment cost in this way comes from the fact that we may now concern ourselves with studying N , the normalized assignment cost, which simplifies much of the computation. Next, we establish some useful facts about the function N . Each fact will be used in bounding the cost in each subcase of Case 5 of Definition 4.

Proof.

(a) This follows directly via simple computation.

(b) This follows directly via simple computation.

Thus upon application of (c), we have

Proof (of Lemma 5). We proceed by showing the claim holds in each potential trigger case of Definition 4. In Cases 1, 2, and 3, the claim trivially holds, because ρ i is assigned greedily to s j . It remains to consider Case 5. Suppose ρ i appeared in between adjacent available servers s ρ(h) and s ρ(h+1) , and let m be the midpoint of s ρ(h) , s ρ(h+1) . Suppose that under the linear transformation L h : s ρ(h) , s ρ(h+1) → (0, 1), ρ i maps to α, y ℓ maps to β ℓ , and y r maps to β r . Further, m trivially maps to 1 2 . In comparing the costs of assignments in s ρ(h) , s ρ(h+1) , it suffices to compare the costs of the normalized assignments in (0, 1), given the normalization factor of s ρ(h+1)s ρ(h) is always the same.

Let p ℓ = R(s ρ(h) , y ℓ , s ρ(h+1) ) and p r = R(s ρ(h) , y r , s ρ(h+1) ). Lemma 11 cleanly handles each subcase of Case 5.

(a) If p r < 1 2 , then ρ i mimics the assignment of a request arriving at y r . We know α ≤ β r , and so N (α, p r ) ≤ N (β r , p r ). (b) Else if p ℓ > 1 2 , then ρ i mimics the assignment of a request appearing at y ℓ . We know α ≥ β ℓ , and so N (α, p ℓ ) ≤ N (β ℓ , p ℓ ). (c) Else if ρ i < m, then ρ i mimics the assignment of a request appearing at y ℓ .

We know β ℓ ≤ α ≤ 1 2 and p ℓ ≤ 1 2 , and so N (α, p ℓ ) ≤ 2 max (α, N (β ℓ , p ℓ )). Note that α is simply the normalized greedy assignment of ρ i . (d) Else ρ i ≥ m, and ρ i mimics the assignment of a request appearing at y r . We know β r ≥ α ≥ 1 2 and p r ≥ 1 2 , and so N (α, p r ) ≤ 2 max (1α, N (β r , p r )). Note that 1α is simply the normalized greedy assignment of ρ i .

Given ρ i assigns rightwards to s ρ(h+1) with probability p, in all cases, we have

Multiplying both sides by the normalization factor of s ρ(h+1)s ρ(h) gives the desired result.

It remains to bound the cost of all individual non-trigger assignments and the greedy assignment. First, we obtain a bound on the greedy assignment of ρ i . Lemma 12. For a triggering request ρ i , let s be the available server nearest to

Proof. Run the adjustment operation on all requests up to ρ i = r τi-1+1 to generate simulated assigned servers s μ(i,t) and a set of simulated assignments Y i = τi-1 t=1 r t , s μ(i,t) solely for the purposes of our argumentation. This produces a set of imaginary servers S ι . Cover the line with the edges in Y i and the assigned edges i-1 j=0 W j ∪ E i-1 . This covering partitions the line into disjoint intervals for which each interval has the same number of requests, servers in Y i , and previously assigned servers in {s σ (1) , s σ(2) , . . . , s σ(τi-1) }. By extension, each partition must have the same number of imaginary servers in S ι and available servers in S ρ . Now pick an imaginary server s γ(t ) for the triggering request ρ i in the same way we picked s γ(t ) , where here t = τ i-1 + 1. This gives a generated imaginary move f i = r t , s γ(t ) , and add f i to this covering. From ρ i , follow f i , reaching a (previously) imaginary server s ι(g) ∈ S ι . Some available server must exist within the partition containing s ι(g) , and so the triangle inequality ensures that some available server exists at most distance

j=0 |W j | from ρ i . Given s is the available server nearest to ρ i , we must have

where in the final step we apply Lemma 7.

Next, we obtain a bound on assignments of requests appearing at non-trigger points, which is a direct corollary from Lemma 9.

Corollary 1. For a non-trigger point y, let s be the available server that Modified Doubled Harmonic would have assigned a request arriving at y, given the estimate is currently

With all of the pieces in place, we establish a cost bound on E [|e i |].

Proof. The proof follows directly from application of Lemma 5, Corollary 1, and Lemma 12. Note that we apply Corollary 1 when the estimate is Z = Z i-1 because ρ i causes the estimate to inflate from Z = Z i-1 to Z = Z i .

We now make the recursive bounds on E We now proceed by induction on i. The base case of |W 0 | = 0 is trivial, and simply define |e 0 | = 0. Let i ∈ [0, m -1] be arbitrary, and assume the claim holds for all j ∈ [0, i]. Then

completing the induction.

Finally, we now prove Theorem 2. The O(log n)-competitiveness of Modified Doubled Harmonic is a direct consequence of Lemma 14 and the the geometric sums are asymtotically equal to their largest summand.