交替子序列的在线算法

Question

考虑一个序列A = a1，a2，a3，.整数的。子序列B of A是序列B = b1，b2，.，bn，它是从A创建的，它删除了一些元素，但保持了顺序。给定整数序列A，目标是计算一个交替子序列B，即序列b1，.bn，使得对于{2，3，…，m-1}中的所有i，如果b{i-1} < b{i}然后b{i} > b{i+1}，如果b{i-1} > b{i}则b{i} < b{i+1}**

考虑这个问题的在线版本，其中序列A是逐元素给出的，每次都需要直接决定是否将下一个元素包含在子序列B中。是否有可能实现恒定的竞争比率(使用确定性的在线算法)？要么给出一个实现恒定竞争比的在线算法，要么说明找不到这样的在线算法。

假设序列9、8、9、8、9、8、.，9，8，8，8，2，1，2，9，8，9，.，8，9，8，8，9，9

我的论点是:算法必须立即决定是否将一个传入数字插入到子序列中。如果算法现在得到数字1，然后2，则最终确定它们是序列的一部分，从而由一个比n-3的最优解更糟糕的非线性因子。

->没有恒定的竞争比率！

这是一个恰当的论证吗？

Answer 1

如果我理解你的意思，你的论点是正确的，但你在这个例子中给出的顺序是错误的。例如，算法可以选择所有的9和8。

您可以稍微修改您的论点，以使其更准确，例如，考虑顺序。

3,4,3,4,3,4,......, 1/5,2/6,1/5,2/6,....

解释：

您可以使用3,4,3,4,...等开始序列，直到算法选择两个数字。如果它从来没有这样做，它显然是没有竞争力的(它使0/1摆脱了n)

如果算法选择了一个3，那么4，则该算法接下来必须取一个低于4的数字。通过继续使用5,6,5,6,...，该算法不能再取另一个数字。

如果算法选择接受一个4，然后是一个3，通过类似的重发，我们可以很容易地看到，继续使用1,2,1,2,...是如何防止算法再使用另一个nubmer。

因此，在任何情况下，算法对每个2都不能超过n数，正如您所说的，这不是一个恒定的竞争比率。