交替子序列的在线算法方法
Online Algorithm approach for alternating subsequence
Consider a sequence A = a1, a2, a3, ... an of integers. A subsequence B of A is a sequence B = b1, b2, .... ,bn which is created from A by removing some elements but by keeping the order. Given an integer sequence A, the goal is to compute an alternating subsequence B, i.e. a sequence b1, ... bn such that for all i in {2, 3, ... , m-1}, if b{i-1} < b{i} then b{i} > b{i+1} and if b{i-1} > b{i} then b{i} < b{i+1}**
Consider an online version of the problem, where the sequence A is given element-by-element and each time, one needs to directly decide whether to include the next element in the subsequence B. Is it possible to achieve a constant competitive ratio (by using a deterministic online algorithm)? Either give an online algorithm which achieves a constant competitive ratio or show that it is not possible to find such an online algorithm.
假设序列 [9,8,9,8,9,8, .... , 9,8,9,8,2,1,2,9,8,9, ... , 8 ,9,8,9,8,9]
我的论点：
该算法必须立即决定是否将传入数字插入到子序列中。如果算法现在得到数字 1 然后 2 然后 2 它最终将决定它们是序列的一部分，因此非线性因素比 n-3 的最优解更差。
->没有恒定的竞争比！
这样的论证合适吗？
如果我理解你的意思，你的论点是正确的，但是你在例子中给出的顺序是错误的。例如，算法可能会选择所有的 9 和 8。
您可以稍微改变您的论点以使其更准确，例如考虑序列
3,4,3,4,3,4,......, 1/5,2/6,1/5,2/6,....
解释：
您以 3,4,3,4,... 等开始序列，直到算法选择两个数字。如果它从来没有，它显然没有竞争力（它从 n 中得到 0/1）
如果算法选择了 3，然后 4，则算法接下来必须取一个小于 4 的数字。通过继续 5,6,5,6,... 算法不能再取另一个数字。
如果算法选择取 4 然后 3，通过类似的共振，我们可以很容易地看到继续使用 1,2,1,2,... 如何防止算法取另一个数字。
因此，在任何情况下，该算法不能为每个 n 取超过 2 个数字，正如您所说，这不是一个恒定的竞争比率。
Consider a sequence A = a1, a2, a3, ... an of integers. A subsequence B of A is a sequence B = b1, b2, .... ,bn which is created from A by removing some elements but by keeping the order. Given an integer sequence A, the goal is to compute an alternating subsequence B, i.e. a sequence b1, ... bn such that for all i in {2, 3, ... , m-1}, if b{i-1} < b{i} then b{i} > b{i+1} and if b{i-1} > b{i} then b{i} < b{i+1}**
Consider an online version of the problem, where the sequence A is given element-by-element and each time, one needs to directly decide whether to include the next element in the subsequence B. Is it possible to achieve a constant competitive ratio (by using a deterministic online algorithm)? Either give an online algorithm which achieves a constant competitive ratio or show that it is not possible to find such an online algorithm.
假设序列 [9,8,9,8,9,8, .... , 9,8,9,8,2,1,2,9,8,9, ... , 8 ,9,8,9,8,9]
我的论点： 该算法必须立即决定是否将传入数字插入到子序列中。如果算法现在得到数字 1 然后 2 然后 2 它最终将决定它们是序列的一部分，因此非线性因素比 n-3 的最优解更差。
->没有恒定的竞争比！
这样的论证合适吗？
如果我理解你的意思，你的论点是正确的，但是你在例子中给出的顺序是错误的。例如，算法可能会选择所有的 9 和 8。
您可以稍微改变您的论点以使其更准确，例如考虑序列
3,4,3,4,3,4,......, 1/5,2/6,1/5,2/6,....
解释：
您以 3,4,3,4,... 等开始序列，直到算法选择两个数字。如果它从来没有，它显然没有竞争力（它从 n 中得到 0/1）
如果算法选择了 3，然后 4，则算法接下来必须取一个小于 4 的数字。通过继续 5,6,5,6,... 算法不能再取另一个数字。
如果算法选择取 4 然后 3，通过类似的共振，我们可以很容易地看到继续使用 1,2,1,2,... 如何防止算法取另一个数字。
因此，在任何情况下，该算法不能为每个 n 取超过 2 个数字，正如您所说，这不是一个恒定的竞争比率。