Better Bounds on the Accommodating Ratio for the Seat Reservation Problem

Abstract

In a recent paper , the seat reservation problem was investigated. It was shown that for the unit price problem where all tickets have the same price, all fair algorithms are at least 1=2-accommodating, while no fair algorithm is more than (4=5 O (1=k))-accommodating, where k is the number of stations the train travels. In this paper, we design a more dextrous adversary.

,

Keywords: The seat reservation problem, on-line algorithms, accommodating ratio, adversary argument.

Introudction

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. Thus, 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 first 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 lt; 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 passengers trip, the passenger must be assigned a seat. An on-line 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 [5] 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, 4, 8, 13], call control [2], interval graph coloring [11] and interval scheduling [12]. The o-line version of the seat reservation problem can be used to solve the following problems [7]: 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 assigning vacation bungalows (mentioned in [14]).

The performance of an on-line algorithm A is usually analyzed by comparing with an optimal o-line algorithm. For a sequence of requests, I , define the competitive ratio of algorithm A applied to I to be the income of algorithm A over the optimal income (achieved by the optimal o-line algorithm). The competitive ratio of algorithm A is the inmum over all possible sequences of requests. The definition of the accommodating ratio [5, 6] of algorithm A is similar to that of the competitive ratio, except that the only sequences of requests allowed are sequences for which the optimal o-line algorithm could accommodate all requests therein. This restriction is used to reflect the assumption that the decision as to how many cars the train should have is based on expected ticket demand. Note that since the input sequences are restricted and this is a maximization problem, the accommodative ratio is always at least as large as the competitive ratio. Formally, the accommodating ratio is defined as follows:

1. Previous results

First, we note that in the case where there are enough seats to accommodate all requests, the optimal o-line algorithm is polynomial time [9] since it is a matter of coloring an interval graph with the minimum number of colors. As interval graphs are perfect [10], the size of the largest clique is exactly the number of colors needed. Let ( k mod 3) denote the residue of k divided by 3, we have the following known results:

Theorem 1.1 [5] Any fair (deterministic or randomized) on-line algorithm for the unit price problem is at least 1=2-accommodating.

Theorem 1.2 [5] No fair (deterministic or randomized) on-line algorithm for the unit price problem (k 6) is more than (8k 8(k mod 3) 9)=(10k 10(k mod 3) 15)-accommodating.

Theorem 1.2 shows that no fair on-line algorithm has an accommodating ratio much better than 4=5. It is also proven in [5] that the algorithms First-Fit and Best-Fit are at most k=(2k6)-accommodating, which is asymptotically 1=2. Let A denote the asymptotic accommodating ratio of a fair on-line algorithm A as k approaches infinity, then the above two theorems show that 1=2 A 4=5. The lower bound 1=2 is achieved by First-Fit and Best-Fit. This leaves the open problem as to whether or not a better algorithm exists [5].

2. Our Contributions

In the next section, we lower the asymptotic upper bound on the accommodating ratio from 4=5 to (7k 15)=(9k 27), and later show that this upper bound holds, even for fair randomized algorithms against oblivious adversaries. For deterministic algorithms, the upper bound is lowered to approximately .7699. It is shown that better upper bounds exist for the special cases with n = 2, 3, and 4 seats. A concrete on-line algorithm First-Fit is examined with regards to the unit price problem for the special case n = 2, and we show it to be asymptotically optimal. We show that First-Fit is ck-accommodating, where ck approaches 3=5 as k approaches infinity.

A General Upper Boun

剩余内容已隐藏，支付完成后下载完整资料

座位预留问题的可容纳率的更好界限

摘要

在最近的一篇论文中，我们对座位预订问题进行了调查。结果表明，对于所有车票价格相同的单价问题，所有公平算法至少为1=2可，而没有公平算法超过(4=5 O(1=k))，其中k为列车行驶的车站数。在本文中，我们设计了一个更灵巧的对手。

,

关键词：座位预订问题，在线算法，适应比例，对手论证。

介绍

在许多火车运输系统中，乘客被要求用火车票预订座位。售票系统必须在乘客购票时分配一个座位，而不知道未来会有什么座位要求。因此，座位预订问题是一个在线问题。因此，竞争分析是合适的。

假设有n个座位的火车从一个起点站开到一个终点站，在k2站停靠，包括第一个站和最后一个站。座位的编号从1到n。起点为1站，终点站为k站。从车站到车站的任何行程，只要1lt;。在购买机票时，每位乘客都有一个座位号，可以在出发前的任何时间办理。如果乘客试图预订时，算法（售票代理）不得拒绝他。也就是说，如果在该乘客的整个旅程中有任何座位是空的，就必须为该乘客分配一个座位。这种在线算法是公平的。

这些算法试图最大化收入，即销售门票价格的总和。当然，在线算法的性能将取决于火车票的定价策略。在[5]中，考虑了两种定价政策：一种是所有的票都有相同的价格，即单价问题；另一种是一张票的价格与旅行的距离成正比，即比例价格问题。本文主要研究了单价问题的公平算法。

座椅保留问题与具有多个波长[1,4,8,13]的光路由、呼叫控制[2]、间隔图着色[11]和间隔调度[12]的问题密切相关。座位保留问题的o线版本可用于解决以下问题[7]：最小化本地寄存器分配中的泄漏，具有开始和结束时间的作业调度，以及VLSI设计中的两点网的路由。该问题的在线版本的另一个应用程序可能是分配度假平房（在[14]中提到的）。

在线算法A的性能通常通过与最优o线算法进行比较来分析。对于一系列请求，I，定义应用于I的算法a的竞争比率为算法A对最优收入(由最优o-line算法实现)的收入。算法A的竞争比是对所有可能的请求序列的总和。算法A的容纳比[5,6]的定义与竞争比的定义相似，除了唯一允许的请求序列是最优o线算法可以容纳其中所有请求的序列。这一限制被用来反映这样一种假设，即决定火车应该有多少节车厢是基于预期的车票需求。请注意，由于输入序列是受到限制的，而且这是一个最大化问题，因此调节比率总是至少与竞争比率一样大。在形式上，容纳比率的定义如下：

1.以前的结果

首先，我们注意到，在有足够的座位容纳所有请求的情况下，最优o线算法是多项式时间[9]，因为它是用最小颜色着色区间图的问题。由于区间图是完美的[10]，最大的团的大小正是所需的颜色的数量。设(kmod3)表示k的残差除以3，我们得到以下已知的结果：

定理1.1[5]针对单价问题的任何公平（确定性或随机）在线算法都至少适合1=2。

定理1.2[5]对于单价问题(k6)没有公平（确定性或随机）在线算法超过(8.8k8(kmod3)9)=(10k10(kmod3)15)。

定理1.2表明，没有公平在线算法的适应比4=5。在[5]中也证明了第一拟合和最佳拟合算法最多可容纳k=(2k6)，且渐近为1=2。设A表示公平在线算法A在k趋近于无穷时的渐近适应比，则上述两个定理证明了1=2A4=5。下界1=2是通过第一拟合和最佳拟合来实现的。这就留下了一个更好的算法是否存在[5]的开放性问题。

2我们的贡献

在下一节中，我们将容纳比的渐近上界从4=5降至(7k15)=(9k27)，然后证明这个上界是成立的，即使对于公平的随机算法也是如此。对于确定性算法，上界被降低到近似，证明了在有n个=2、3和4个座位的特殊情况下存在更好的上界。.7699.针对特殊情况n=2的单价问题，研究了一个具体的在线算法第一拟合，并证明了它是渐近最优的。我们证明了第一Fit是ck适应的，当k趋于无穷时，ck接近3=5。

一般上界

容纳比的上限降低，首先为7=9，之后约为7699。

定理2.1单价问题（k9）没有确定性公平在线算法大于f(k)。

这个定理的证明是一个对立的论证，它是一个更多的基于[5]中定理1.2证明的思想的设计。假设n可以被2整除。对手开始n=2请求间隔[3s 1；3s 3]s=0；1；；b(k3)=3c。任何公平的在线算法都能够满足这一组bk=3cn=2请求。假设在这些请求得到满足后，存在同时包含间隔[3i 1；3i 3]和间隔[3i 4；3i 6]，i=0；1；；b(k6)=3c。然后是从3i 2站到3i 5站的气座位是空的。

在下面的内容中，我们不是一次考虑每个气（如[5]），而是考虑q2i；q2i 1一起为i=0；1；；b(k9)=6c。设pi=q2i q2i 1(n)。我们区分了以下两种情况：

案例1：pi5n=9；和

案例2：pigt;5n=9。

在第一种情况下，pi5n=9，对手继续n=2请求间隔[6i 2；6i 5]，n=2请求间隔[6i 5；6i 8]。对于这n个附加请求，在线算法可以精确地容纳它们的pi。图1(a)显示了此配置。因此，对于启动站s2[6i 1；6i 6]的2n个请求，在线算法容纳它们的n pi。

在第二种情况下，pigt;5n=9，对手继续n=2请求间隔[6i 3；6i 7]，然后n=2请求间隔[6i 2；6i 4]。

这样，请求被划分为b(k3)=6c 1组；第一个b(k3)=6c组包含2n或5n个=2请求，最后一个组包括n个(如果(kmod6)2f0；1；2g)或n个=2(如果(kmod6)2f3；4；5g)请求。对于第一b(k3)=6c组中的每一个，在线算法可以容纳其中多达7=9的请求。这就引出了这个定理。更准确地说，让S表示发生第一种情况的索引集，让S表示发生第二种情况的索引集。当(kmod6)2f0；1；2g时，该公平在线算法的适应率应用于此请求序列。

随机算法

定理4.1对于单位问题(k9)的随机公平在线算法不超过f(k)的适应性，这是定理2.1的证明。遗忘对手所使用的请求序列取决于所定义的pi=q2i q2i 1的期望值 在 那 证明 的 定理 2.1. 这个 在定理2.1的证明中，被遗忘的对手以与对手相同的顺序开始。然后，对于每个i=0；1；；b(k9)=6c，它根据期望值E[pi]与5n=9相比，决定案例1或案例2。通过生成相应的请求，期望的线性性意味着随机算法所容纳的期望请求的数量最多是一个分数。

虽然可以直接证明定理2.1也适用于随机算法，但如上所示，我们不能使用相同的论点，而对其他定理显示相同的论点。事实上，我们可以证明定理两个座位，考虑请求在S中的两个座位上的任何最优位置。根据它们在这个位置中出现的位置，我们现在将请求称为座位1和座位2的请求或间隔。

根据Seat1的请求，我们将这些请求划分为连续的组。我们为每个组显示，在平摊的意义上，该组中所接受的预期请求数至少为34个。这两个座位的命名显然是任意的；我们使用以下编号：座位2是包含最小起始编号的间隔的座位。如果有两个间隔与同一启动站，则座位2是包含这两个间隔中较长的一个座位。（如果这两个间隔相同，则它们都将被接受，因此可以忽略它们，而可以使用下一个间隔。）另一个座位是座位1号。

座位1，要求我。如果没有座位1请求K与I重叠，并延伸到右边，那么该组只包括I和座位1间隔的一些数字x，它们包含在区间I中。下一组的定义将通过考虑不早于I的终端站开始并以第一组开始的请求，可能重新命名座位。这种情况没有提供任何问题，所以假设这个请求K存在。

所有作为I或K的子间隔的请求都包含在这个组中，I和K也是如此。下面，我们假设在请求序列中有I的x0子区间，K的y0子区间。因此，整个组由2个 x 请求组成，所有这些都被最优 线算法接受。可能存在来自前一个组重叠I的Seat1请求。调用那个请求为L。类似地，间隔K可能重叠来自下一组的Seat2请求(来自下一组的I间隔)，我们在这里称之为J。

证明是基于请求序列中相关间隔的冗长的案例分析。由于包含在I和K中的 区间总是被接受的，只有假设它们在I和K之前，比率才会变得更糟，所以我们做出这个假设。同样地，我们假设如果L在I之前，那么L被接受，如果J在K之前，那么J被接受。如果L或J不存在，则将组处理得好像它们在I或K之后。案例分析工作见下表。表示法I1，I2”表示在请求序列中I1出现在I2之前。符号的“表示xgt;0，ylsquo;s”表示ygt;0。表中的标记，，表示给定的谓词为true；否则为false。有32个案例。对于每一个，计算I被接受的概率Prob(I)和K被接受的概率Prob(K)，并给出一个结果，结果。对于给出的两个区间I和K中的第一个，它被接受的概率是在它之前没有一个重叠的两个区间被放置在不同的座位上的概率。由于这些其他的间隔在座位1上同样有可能出现，所以这个概率是u1，其中u是干扰间隔的数量。接受I和K的第二个区间的概率计算得类似，但通过加权第一个区间是否被接受的概率的两种可能情况。结果”，计算为，是该组中被接受的区间的期望分数。所有的结果都是使用x和y的值来计算的，这些值给出了最小值的结果（参见下面如何定义这个最小值）。在大多数情况下，将它们设置为1会得到最小值。例外情况是情况9和13，其中=1和y=2；17和21其中=2和y=110182230其中=2；1115152327其中y=2；25和29其中=2和=2；26其中=3；31其中y=3。

,

摊销用于处理当L和J同时发生在I和K之前的最坏情况发生的问题，但这不能发生在两个连续的组中。例如，如果一组类型27发生在一组类型1之前，那么案例27中的额外期望14可以用于（超过）覆盖案例1中18的赤字，因此总体上期望足够高。

调用属于前8种情况（图4中）晚组的组，因为它们的I和K间隔在请求序列中比周围两个组的相关间隔晚。同样地，分为最后8例早期组，9到16晚期早期组，以及17到24早期晚期组。在图4的结果”列中，小于34的分数表示为34wzw，其中w=2 x y是组中的间隔数。我们把值z称为这个群体的赤字。

请注意，赤字永远不会超过一个间隔的18，这些只发生在晚期组。对于早期的组，“结果”表示为，这里的值z是组的盈余。所有早期的群体都有至少14人的盈余，这超过了任何晚期群体的赤字。(请注意，在计算最小值时，计算它们是为了最大化赤字或最小化盈余，而不是为了最小化所接受的预期分数。只有25和29组会产生作用。)显然，定义的第一组没有请求L，所以它要么是早期组，要么是早期-晚期组。虽然不能假设每个晚期组在其之前都有一个早期组，但很容易看到，对于每个晚期组，在请求序列之前必须有一些早期组。这个早期群体的盈余不仅可以弥补晚期群体的赤字。所有的早期-晚期和晚期-早期组都是这样的，在这些组中被接受的间隔的预期比例至少是34，所以被接受的间隔的总预期比例至少是34。事实上，当有n个=2个座位时，这个值34是随机容纳比的一个非常紧的下限。