Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem.
The unit price seat reservation problem is investigated. The seat reservation problem is the problem of assigning seat numbers on-line to requests for reservations in a train traveling through k stations. We are considering the version where all tickets have the same price and where requests are treated fairly, that is, a request which can be fulfilled must be granted.For fair deterministic algorithms, we provide an asymptotically matching upper bound to the existing lower bound which states that all fair algorithms for this problem are -competitive on accommodating sequences, when there are at least three seats.Additionally, we give an asymptotic upper bound of 7/9 for fair randomized algorithms against oblivious adversaries.We also examine concrete on-line algorithms, First-Fit and Random for the special case of two seats. Tight analyses of their performance are given.
Introduction
In many train transportation systems, passengers are required to buy seat
reservations with their train tickets. The ticketing system must assign a passenger
a single seat when that passenger purchases a ticket, without knowing
what future requests there will be for seats. Therefore, the seat reservation
problem is an on-line problem, and a competitive analysis is appropriate.
Assume that a train with n seats travels from a start station to an end
station, stopping at k  2 stations, including the rst and the last. The
seats are numbered from 1 to n. The start station is station 1 and the end
station is station k. Reservations can be made for any trip from a station
s to a station t as long as 1  s < t  k. Each passenger is given a single
seat number when the ticket is purchased, which can be any time before
departure. The algorithms (ticket agents) may not refuse a passenger if it
is possible to accommodate him when he attempts to make his reservation.
That is, if there is any seat which is empty for the entire duration of that
passenger's trip, the passenger must be assigned a seat. An algorithm of this
kind is fair.
The algorithms attempt to maximize income, i.e., the sum of the prices of
the tickets sold. Naturally, the performance of an on-line algorithm will depend
on the pricing policies for the train tickets. In [6], two pricing policies
are considered: one in which all tickets have the same price, the unit price
problem; and one in which the price of a ticket is proportional to the distance
traveled, the proportional price problem. This paper focuses on fair
algorithms for the unit price problem.
The seat reservation problem is closely related to the problem of optical
routing with a number of wavelengths [1, 5, 9, 14], call control [2], interval
graph coloring [12] and interval scheduling [13]. The o-line version of the
seat reservation problem can be used to solve the following problems [8]:
minimizing spill in local register allocation, job scheduling with start and end
times, and routing of two point nets in VLSI design. Another application
of the on-line version of the problem could be to assign vacation bungalows
(mentioned in [15]).
The performance of an on-line algorithm A is usually analyzed using the
competitive ratio dened in the following way.
Denition 1.1 Let A(I) denote how much an on-line algorithm A earns
with the request sequence I, and let OPT(I) denote how much is earned
by an optimal o-line algorithm when given the sequence I. An on-line
algorithm A is c-competitive if, for any sequence I of requests, A(I)  c
is a constant which does not depend on the input
sequence I. The competitive ratio for A is the supremum over all such c. 2
Note that in general the constant b is allowed to depend on k. This is because
k is a parameter to the problem, and we quantify rst over k. Notice that
the fairness criterion dened above is a part of the problem specication.
Thus, even though the optimal o-line algorithm knows the whole sequence
of requests in advance, it must process the requests in the same order as the
on-line algorithm, and do so fairly.
In this paper, we investigate the competitive ratio in the special case where
there are enough seats to accommodate all requests, i.e. an optimal o-line
algorithm will not reject any of the requests. This restriction on the input
sequences is used to re
ect the assumption that the decision as to how many
cars the train should have is based on expected ticket demand.
Denition 1.2 A sequence of requests that can be fully accommodated by
an optimal o-line algorithm is called an accommodating sequence. 2
In earlier papers [6, 7], the competitive ratio on accommodating sequences
was called the accommodating ratio. The change is made here for consistency
with common practice in the eld.
1.1 Coloring Interval Graphs
Since we are only considering the unit price problem, the seat reservation
problem is similar to the problem of coloring an interval graph on-line. This
is easy to see. The route the train travels from station 1 through station k
is the section of the real line considered. The part of the route a passenger
travels is an open interval, and the seat the passenger is assigned is the color
the interval is given.
Note that in the case where there are enough seats to accommodate all re-
quests, the restriction that the optimal o-line algorithm be fair is in fact no
restriction. Thus, the optimal fair o-line algorithm is polynomial time [10]
since it is simply a matter of coloring an interval graph with the minimum
number of colors. Recall that interval graphs are perfect [11], so the size of
the largest clique is exactly the number of colors needed. Thus, when there
is no pair of stations (s; s + 1) such that the number of people who want to
be on the train between stations s and s + 1 is greater than n, the optimal
fair o-line algorithm will be able to accommodate all requests. The contrapositive
is clearly also true; if there is a pair of stations such that the number
of people who want to be on the train between those stations is greater than
n, the optimal fair o-line algorithm will be unable to accommodate all re-
quests. We will refer to the number of people who want to be on the train
between two stations as the density between those stations.
1.2 Previous Results
We have the following known results:
Theorem 1.1 [6] On accommodating sequences, any fair (deterministic
or randomized) on-line algorithm for the unit price problem is at least 1-
competitive. 2
Theorem 1.2 [6] Even on accommodating sequences, no fair (deterministic
or randomized) on-line algorithm for the unit price problem (k  6) is more
than 8k 8(kmod3) 9
-competitive. 2
Thus, even on accommodating sequences, no fair randomized on-line algorithm
has a competitive ratio much better than 41.3 Our Contributions
In the next section, we lower the asymptotic upper bound on the competitive
ratio on accommodating sequences for fair deterministic algorithms from 4to 1when k is large compared to n, and n  3. For fair randomized algorithms
against oblivious adversaries, we show an upper bound of 7for large
k. A concrete on-line algorithm, First-Fit, is examined with regards to the
unit price problem for the special case 2. Here, we show that First-Fit
is 3-competitive on accommodating sequences, and we show that this is
asymptotically optimal. Finally, we examine a concrete randomized on-line
algorithm, Random. We prove an asymptotic upper bound of 17for n  3,
and for the special case of asymptotically matching upper and
lower bounds of 3Some of the results in this paper were presented in [4].
Algorithms
In this section, we investigate the competitive ratios of deterministic fair
algorithms for the unit price seat reservation problem. We consider the cases
separately. Trivially, for fair on-line algorithm
is 1-competitive on accommodating sequences.
2.1 A General Upper Bound for n  3
The upper bound on the competitive ratio on accommodating sequences is
lowered to match the lower bound, for k large compared to n.
Theorem 2.1 The competitive ratio on accommodating sequences for the
fair unit price seat reservation problem with 3 seats is at most 1+ 3
, where
Proof First we give intervals of length four with a spacing of two, except
that the rst interval only has length three, and the last has length one. The
intervals are: [1; 4]; [6; 10]; [12; These intervals, which are
referred to as the original intervals, are unnamed in Fig. 1.
Then we give additional requests, processing the already given requests from
left to right, based on how the on-line algorithm has placed the original
intervals. How to give these additional requests, which are named e in the
illustration, is determined during the processing from left to right.
We maintain the invariant depicted in Fig. 1a:
Every interval with its start station to the left of or on the vertical
dotted line has been processed (this includes the extra intervals which
have been given).
Every processed interval, except the rst two all the way to the left,
has an associated \rejected" interval.
e
a) Invariant and base case.
e
b) Next interval with e.
e e ext.
c) Next interval with previous.
ext.
d) Next interval on free.

Figure

1: Cases of the proof.
The only intervals with start station strictly to the right of the vertical
dotted line are the original intervals.
Below the horizontal dotted line, we show the \rejected" intervals. Note that
an optimal o-line algorithm can accommodate all requests, since the density
is no more than three between any two stations, which implies that the clique
number of the corresponding interval graph is at most three.
Establishing the base case can be done by giving the interval
illustrated in Fig. 1a. This interval and the original interval [1; 4] will be the
only ones without associated \rejected" intervals.
Note that this e interval as well as other e intervals to be given later may be
extended during the processing of the next original interval. In the gure,
this is marked with an asterisk.
For the induction step, we assume that we have processed up to a certain
station and have been able to maintain the invariant.
In processing the next original interval, there are three cases: the interval
could be on the same seat as e (Fig. 1b), on the same seat as the previous
original interval (Fig. 1c), or on the third seat (Fig. 1d).
In each case, we must reestablish the invariant six stations further to the
right (the next vertical dotted line).
In Fig. 1b, we give a new interval e 0 which should serve as the e interval in
the next round. The original interval which is processed as well as e 0 get an
associated \rejected" interval.
In Fig. 1c, we extend the already given e interval (in reality, we should
process all intervals to determine what should be given before actually giving
any requests, so we know exactly how long an interval should be when we
actually give it). So, we only need to provide two \rejected" intervals. Again,
will be the new e interval in the next round.
In Fig. 1d, we also extend the e interval, and that interval will also serve as
the e interval in the next around. Thus, only one \rejected" interval for the
processed original interval must be provided.
In summary, we give k+5original intervals, and except for the rst of these,
one \rejected" interval for each. Additionally, we give some number x  1 of
e intervals, and x 1 \rejected" intervals for these. In total, we get the ratio
This term dominates the corresponding term with
above result can easily be extended to any k  7, by giving the same
sequence and ignoring the last few stations. Let c  k 1 (mod 6). The
upper bound is then 1+ 3
k+(5 c)
Corollary 2.1 The competitive ratio on accommodating sequences for the
fair unit price seat reservation problem with n  3 seats is at most 1+
Proof First we give n 3 intervals of the type [1; k]. Because of fairness,
both the on-line as well as the optimal o-line algorithm must accept all
Now use the above theorem on the remaining three seats.
The ratio becomes
which dominates
:The technique of Corollary 2.1 which converts an upper bound for m seats
to an upper bound for n seats (n > m) by adding some large requests in
the beginning of the sequence, can be applied to any sequence. This can be
done both to negative results for deterministic algorithms and to negative
results for randomized algorithms. Thus, the asymptotic competitive ratio is
a monotone non-increasing function of n, if there is no limit on the number
of stations.
2.2 The Case
In this section, the case However, we note that in
train systems, it is unlikely that a train has a small number of seats. So the
bounds obtained here are probably irrelevant for this application, but they
could be relevant for others such as assigning vacation bungalows.
The following theorem gives an upper bound on the competitive ratio on
accommodating sequences for fair algorithms. This bound approaches 3as
approaches innity.
Theorem 2.2 Let
5k 5(k mod
5k 5(k mod
algorithm for the unit price problem
f(k)-competitive, even on accommodating sequences.
Proof The adversary begins with one request for the interval [3s +1; 3s+ 3]
for each
3 c. After these requests are satised by the on-line
algorithm, consider for each
6 c how the three requests
are satised. Suppose that
the intervals [6i are placed on
the same seat. Then the adversary proceeds with a request for the interval
then requests for each of the intervals [6i
8]. The on-line algorithm will accommodate the rst request,
but fail to accommodate the last two. In the second case, suppose only two
adjacent intervals (among [6i
are placed on the same seat, say [6i
the adversary proceeds with three requests for the intervals [6i
8]. The on-line algorithm will accommodate
the rst request but fail to accommodate the last two. In the last case, only
the intervals [6i are placed on the same seat.
Then the adversary proceeds with two requests for the intervals [6i+2; 6i+5]
8]. The on-line algorithm will fail to accommodate both of
them.
It then follows easily that, even on accommodating sequences, the competitive
ratio of the on-line algorithm applied to this sequence of requests is at
most
A specic on-line algorithm called First-Fit always processes a new request by
placing it on the rst seat which is unoccupied for the length of the journey.
The following theorem shows that for First-Fit is an asymptotically
optimal on-line algorithm.
Theorem 2.3 First-Fit for the unit price problem is at least 3-competitive
on accommodating sequences, when 2.
Proof Consider any set of requests which the optimal o-line algorithm
could accommodate with two seats. Let S be the subset of requests accommodated
by First-Fit, and let U denote the subset of unsatised requests.
The non-empty intervals between two consecutive requests satised on some
seat (i.e., the durations in which the seat is empty) are called gaps on that
seat. It can easily be shown that it is impossible that there are two requests
in U whose starting stations are in the same gap, and that no request in U
can have its starting station in a gap on both seats. Partition U into U 1 and
denotes the subset of requests in U with starting station s in
some gap on seat i.
Sort the requests in U i so that their starting stations are in increasing order,
and consider them one-by-one in this order. For each request
denote the request, in S, for the rst interval which prevents
accommodating r on seat 2. Then seat 1 must be empty from station s 1
to station minft; t 1 g. By the First-Fit rule, we have t < t 1 , since otherwise
request r 1 would be accommodated on seat 1. For the same reason, there
should be some request r which is accommodated on seat
We claim that there is no request r
whose starting station s 0 is in the gap right before [s Otherwise, we
would have t 0  s 1 , which ensures that request r 0 could be satised on seat
1. Conceptually, we assign requests r 1 and r 2 in S to request r. Notice that
for dierent r 2 U 2 , the requests r 1 and r 2 in S are dierent.
After nishing the requests in U 2 , we consider the requests in U 1 . For each
request denote the request, in S, for the rst
interval which prevents accommodating r on seat 1. Then seat 2 must be
empty from station s 1 to station minft; t 1 g. Let r denote the last
request that is satised on seat 2 before s 1 . That is, seat 2 is empty from
station t 2 to station minft; t 1 g. Obviously, t 2  s 1 . Furthermore, there is no
request r . If there is no request q 2 U 2
with its starting station in the gap (on seat 2) before s 2 , or there is no such
gap at all, then we assign requests r 1 and r 2 to r. In the case where there
is a gap and there is some request starting station u in
this gap, let q 1 and q 2 denote the two requests in S that were assigned to
q. We then reassign requests r 1 , q 1 and q 2 to requests r and q. Notice that
for dierent r, the corresponding q must be dierent, and the same requests
in S cannot be assigned to dierent requests from U . Thus, depending on
which case we are dealing with, either two requests in S are assigned to one
in U , or a group of three requests in S is assigned to a pair of requests in
U . So the size of U is at most 2the size of S, which means that First-Fit
accommodates at least three-fths of the requests. 2
3 Randomized Algorithms
In this section, we examine the competitive ratios on accommodating sequences
for randomized fair on-line algorithms for the unit price problem,
by comparing them with an oblivious adversary. Some results concerning
randomized fair on-line algorithms for the proportional price problem can be
found in [3].
Though the following theorem is about deterministic algorithms, and the
result is worse than Theorem 2.1, it is included in this section because the
structure of the proof allows for an easy transformation to a proof for the
equivalent randomized problem. We believe it is easier to rst understand
the deterministic proof, and then verify the transformation in the subsequent
corollary.
Theorem 3.1 Let
7k 7(k mod
9k 9(k mod
14k 14(k mod
algorithm for the unit price problem (k
more than f(k)-competitive, even on accommodating sequences.
Proof The proof of this theorem is an adversary argument, which is a more
dextrous design based on the idea in the proof of Theorem 1.2 in [6]. Assume
that n is divisible by 2. The adversary begins with nrequests for the intervals
3 c. Any fair on-line algorithm is able to
satisfy this set of b kc  nrequests. Suppose that after these requests are
satised, there are q i seats which contain both interval [3i
6c. Then there are exactly q i seats
which are empty from station 3i + 2 to station 3i 5.
In the following, rather than considering each q i at a time (as in [6]), we
consider q
We distinguish between two cases:
Case 2: 5nIn the rst case p i  5n, the adversary proceeds with nrequests for the
nrequests for the interval [6i
these n additional requests, the on-line algorithm can accommodate exactly
Fig. 2a shows this conguration. The intervals marked with a \1"
are the intervals which are given rst, i.e., before deciding on Case 1 or 2. The
intervals marked with a \2" are the ones given afterwards. Thus, for those
2n requests whose starting station s 6], the on-line algorithm
accommodates
In the second case p i > 5n, the adversary proceeds with nrequests for the
by nrequests for interval [6i
nrequests for the interval [6i 8]. For these 3nadditional requests,
the on-line algorithm can accommodate exactly 3np i of them. Fig. 2b
shows this conguration. Thus, of the 5nrequests whose starting station
6], the on-line algorithm accommodates 5np i of them.
a)
Figure

2: Example congurations for the two cases.
In this way, the requests are partitioned into b k 3
6 c+1 groups; each of the rst
groups consists of either 2n or 5nrequests and the last group consists
of either n (if (k mod
For each of the rst b k 3c groups, the on-line algorithm can accommodate
up to a fraction 7of the requests therein. This leads to the theorem. More
precisely, let S denote the set of indices for which the rst case happens, and
let
S denote the set of indices for which the second case happens. When
the ratio of the number of requests accepted by the
on-line algorithm to the number of requests accepted by an optimal o-line
algorithm is
5n
9k 9(k mod
where the last inequality holds because in general a
d < 1 and a < c imply
that e+ax+cy
e+bx+dy  e+a(x+y)
. When (k mod 5g, the ratio is
5n
This completes the proof. 2
Corollary 3.1 Let
7k 7(k mod
9k 9(k mod
14k 14(k mod
randomized fair on-line algorithm for the unit price problem (k
more than f(k)-competitive, even on accommodating sequences.
Proof The oblivious adversary behaves similarly to the adversary in the
proof of Theorem 3.1. The sequence of requests employed by the oblivious
adversary depends on the expected values of p are
dened in the proof of Theorem 3.1. The oblivious adversary starts with
the same sequence as the adversary in the proof of Theorem 3.1. Then,
for each
6 c, it decides on Case 1 or Case 2, depending on
the expected value E[p i ] compared with 5n. By generating corresponding
requests, the linearity of expectations implies that the expected number of
requests accommodated by the randomized algorithm is at most a fraction
f(k) of the total number of requests. 2
Although it is straight forward to show that Theorem 3.1 holds for randomized
algorithms, too, as shown above, one cannot use the same argument and
show the same for the other theorems.
The most obvious randomized algorithm to consider for this problem is the
one we call Random. When Random receives a new request and there exists
at least one seat that interval could be placed on, Random chooses randomly
among the seats which are possible, giving all possible seats equal probability.
Theorem 3.2 For for the unit price problem is at least4
-competitive on accommodating sequences.
Proof Given a request sequence S which could be accommodated with two
seats, consider any optimal placement of the requests in S on two seats.
Based on where they appear in this placement, we now refer to requests as
Seat 1 and Seat 2 requests or intervals.
Based on the Seat 1 requests, we partition the requests into consecutive
groups. We show for each group that, in an amortized sense, the expected
number of requests accepted in that group is at least 3The naming of the two seats is clearly arbitrary; we use the following num-
bering: Seat 2 is the seat containing the interval with smallest start station
number. If there are two intervals with that same start station, then Seat 2
is the seat containing the longer of these two intervals. (If the two intervals
are identical, they both will be accepted, so they can be ignored and the next
intervals can be used instead.) The other seat is Seat 1.
In general, a group is dened as depicted in Fig. 3. It starts with a Seat 1
request I. If no Seat 1 request K overlaps I and extends beyond it to
the right, then the group only includes I and some number x of Seat 1
intervals, which are contained in the interval I. The next group will be
dened by considering requests that start no earlier than the end station of
I and beginning as with the rst group, possibly renaming the seats. This
case gives no problem, so assume that this request K exists.
All of the requests which are subintervals of either I or K are included in
this group, as are I and K. In the following, we assume that there are x  0
subintervals of I and y  0 subintervals of K in the request sequence. Thus,
the entire group consists of 2+x+y requests, all of which are accepted by the
optimal o-line algorithm. It may be the case that there is a Seat 1 request
from the previous group overlapping I. Call that request L. Similarly, the
interval K may overlap a Seat 2 request from the next group (the I interval
from the next group), which we call J here.
The proof is a lengthy case analysis based on where the relevant intervals
occur in the request sequence. Since the x+y intervals contained within I and
K are always accepted, the ratio can only become worse if they are assumed
I y's J

Figure

3: A group picture.
to come before I and K, so we make that assumption. Similarly, we assume
that if L comes before I, then L is accepted, and if J comes before K, then J
is accepted. If L or J do not exist, the group is handled as if they came after
I or K. The case analysis is done in the table below. The notation \I 1
indicates that I 1 occurs before I 2 in the request sequence. The notation \x's"
indicates that x > 0 and \y's" indicates that y > 0. A mark, , in the table
indicates that the given predicate is true; otherwise it is false. There are
thirty-two cases. For each one, the probability that I is accepted, Prob(I),
and the probability that K is accepted, are calculated, and a result,
Result, is given. For the rst of the two intervals I and K which is given,
the probability of it being accepted is the probability that no two intervals
which come before it and overlap it are placed on dierent seats. Since these
other intervals are equally likely to be on Seat 1 as Seat 2, this probability
is 1 u 1 , where u is the number of interfering intervals. The probability of
acceptance of the second of I and K is calculated similarly, but by weighting
the two possible cases of whether or not the rst interval is accepted by
the probability that it is accepted. The \Result", which is calculated as
Prob(I)+Prob(K)+x+y
2+x+y
, is the expected fraction of the intervals in that group
which are accepted. All of the results are calculated using those values of x
and y which give the minimum result (see below for how this minimum is
dened). In most cases, setting them equal to 1 gives the minimum. The
exceptions are cases 9 and 13 where
and
The amortization is used to handle the problem that the worst case occurs
when both L and J occur before I and K, but this cannot happen for two
consecutive groups. If, for example, a group of type 27 occurs immediately
before a group of type 1, the extra expectation of 1from case 27 can be
used to (more than) cover the decit of 1from case 1, so that overall the
expectation is high enough.
Call the groups that fall into the rst eight cases (in Figure 4) late groups,
since their I and K intervals occur later in the request sequence than the
relevant intervals from the two surrounding groups. Similarly, call the groups
that fall into the last eight cases early groups, those that fall into cases 9
through late-early groups, and those that fall into cases 17 through 24
early-late groups. In the \Result" column of Fig. 4, fractions which are less
than 3are expressed as4 w z
y is the number of intervals
in the group. We refer to the value z as the decit for the group. Notice that
there is never a decit greater than 1of an interval, and these only occur
for late groups. For the early groups, the \Result" is expressed as4 w+z
and here the value z is the surplus for the group. All of the early groups
have a surplus of at least 1, which more than covers the decit of any late
group. (Note that when the minimums were calculated, they were calculated
to maximize the decit or minimize the surplus, rather than to minimize the
expected fraction accepted. It is only groups 25 and 29 where this makes a
dierence.) Clearly, the rst group dened has no request L, so it is either
an early group or an early-late group. Although one cannot assume that
each late group has an early group immediately preceding it, it is easy to see
that for each late group there must be some some early group before it in
the request sequence. The surplus of this early group can more than cover
the decit of the late group. All of the early-late and late-early groups are
such that the expected fraction of the intervals in those groups accepted is
at least 3, so the total expected fraction of intervals accepted is at least 32
This value of 3is, in fact, a very tight lower bound on Random's competitive
ratio on accommodating sequences when there are seats.
Theorem 3.3 Let
For for the unit price problem (k  3) is at most f(k)-
competitive on accommodating sequences.
Proof We rst give the request [1; 2] and then the requests
2cg. If k is odd, we then give the request [k
Random will place each of these requests, and, since there is no overlap, they
are placed on the rst seat with probability 1Now we continue the sequence with [2i 3cg.
Each interval in this last part of the sequence overlaps exactly two intervals
from earlier and can therefore be accommodated if and only if these two
intervals are placed on the same seat. This happens with probability 1
No. L,I J ,K I,K x's y's Prob(I) Prob(K) Result
26   1x
28

Figure

4: Table of dierent groups.
Thus, all requests from the rst part of the sequence, and expected about
half of the requests for the last part, are accepted. More precisely we obtain:
f(k):The competitive ratio of 3on accommodating sequences for Random with
seats does not extend to more seats. In general, one can show that
Random's competitive ratio on accommodating sequences is bounded from
above by approximately 17= 0:7083  3.
Theorem 3.4 Even on accommodating sequences, the competitive ratio for
Random is at most 17k+14
, for the unit price problem, when k  2 (mod 4).
Proof Assume that n is divisible by 3. The request sequence is as follows:
[1; 2] | ntimes.
ntimes | for ntimes.
ntimes | for ntimes.
ntimes | for 4These will be referred to as the extra intervals.
If First-Fit was applied on this sequence, all knrequests would be accom-
modated. Random will accommodate everything except some of the extra
intervals. In what follows, the intervals of length shorter than 4, which are
not extra intervals, will be thought of as if they had length 4 and thus extended
before the rst station or after the last. Notice that m extra intervals
of the form [4s+1; 4s+3] will be accepted if and only if exactly m seats which
receive the interval [4s 2; 4s receive the interval [4s
Similarly, m extra intervals of the form [4s 5] will be accepted if
and only if exactly m seats which receive the interval [4s; 4s receive
the interval [4s us consider the types of extra intervals in
Combinations Expected
[4s
n=27
2n=27
2n=27
2n=27
4n=27
4n=27
n=9
2n=9

Figure

5: The expected number of seats with various combinations of the
intervals.
pairs ([4s +1; 4s+ 3]; [4s +3; 4s+ 5]) to calculate the expected number which
are accommodated by Random. Consider all but the last pair of these extra
intervals. The intervals which can interfere with whether or not these
extra intervals are accommodated are those of the forms [4s 2; 4s
8]. The only other intervals which can
aect where any of these are placed, relative to each other, are those of the
form [4s+6; 4s+10]. When the intervals [4s 2; 4s+2] are placed, the probability
for each one that it will have an interval [4s immediately
after it is 1. Thus one expects that 1of the [4s will be
accepted. The intervals of the form [4s; 4s+ 4] cannot be on the same seat as
any [4s 2; 4s interval. The table in Fig. 5 shows the
expected number of seats which will be assigned the various combinations of
the intervals [4s 2; 4s
An \" indicates the presence of an interval of that type.
The intervals of the form [4s only go where there is neither
One can see from the
above table that the expected number of seats like this is 4n. The expected
number of them that have a [4s; 4s + 4] interval is 2n, so one expects 1of
the intervals of the form [4s 5] to be accommodated. A similar,
but simplied argument gives exactly the same expectations for the last
two types of extra intervals. This gives that the expected number of extra
intervals accommodated by Random is n( 1+ 1) k 2= 5nk 2. Hence, the
ratio of the number of requests accommodated by Random to the number of
requests given is n
. 2
For other k, not congruent to 2 modulo 4, and other n  3, not congruent to 0
modulo 3, similar results hold. Giving rst n mod 3 [1; k] requests, and then
using the same sequence of requests as in the previous proof (and thus not
using the last stations), gives upper bounds of the form 17k c 1
for constants
c 1 and c 2 which depend only on the value of k mod 4.
Concluding Remarks
We have shown that any fair deterministic algorithm for the unit price seat
reservation problem has an asymptotic competitive ratio of 1on accommodating
sequences. The most interesting open problem remaining here is
whether or not there exists a randomized algorithm which does better. In
particular, what is the competitive ratio of the algorithm Random on accommodating
sequences? We have shown that it is 3when no more
than 17for n  3. However, the best known lower bound on its performance
is still 1for n  3.

Acknowledgments

Bach was supported in part by NSF Grant CCR-9510244.
Joan Boyar would like to thank Faith Fich for interesting discussions regarding
the seat reservation problem with seats.
Joan Boyar and Kim S. Larsen carried out part of this work while visiting
the Department of Computer Sciences, University of Wisconsin { Madison.
They were supported in part by SNF (Denmark), in part by NSF (U.S.)
grant CCR-9510244, in part by the esprit Long Term Research Programme
of the EU under project number 20244 (alcom-it).
Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen were supported in part
by the IST Programme of the EU under contract number IST-1999-14186
(alcom-ft).
Tao Jiang and Guo-Hui Lin were supported in part by NSERC Research
Grant OGP0046613 and a CITO grant.
Tao Jiang was supported in part by a UCR startup grant.
Rob van Stee was supported by the Netherlands Organization for Scientic
Research (NWO), project number SION 612-30-002.



--R



The Accommodating Ratio for the Seat Reservation Problem
Better Bounds on the Accommodating Ratio for the Seat Reservation Problem

The Seat Reservation Problem
The Accommodating Function
On the k-Coloring of Intervals

Algorithms for Minimum Coloring
Graph Coloring Problems Wiley



Exact and Approximation Algorithms for the Operational Fixed Interval Scheduling Problem
--TR
Efficient routing in all-optical networks
Bandwidth allocation with preemption
Efficient on-line call control algorithms
Online interval scheduling
Competitive non-preemptive call control
On the k-Coloring of Intervals
The Accommodating Function - A Generalization of the Competitive Ratio
Better Bounds on the Accommodating Ratio for the Seat Reservation Problem
On-line Competive Algorithms for Call Admission in Optical Networks
The Accommodating Ratio for the Seat Reservation Problem

--CTR
Joan Boyar , Susan Krarup , Morten N. Nielsen, Seat reservation allowing seat changes, Journal of Algorithms, v.52 n.2, p.169-192, August 2004
Marek Chrobak, SIGACT news online algorithms column 8, ACM SIGACT News, v.36 n.3, September 2005
accomodating sequences;competitive ratio;seat reservation problem;on-line algorithms