Robust Algorithms under Adversarial Injections
Robust Algorithms under Adversarial Injections
复制标题
对抗性注入下的鲁棒算法
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
O. Svensson
中科院分区：
文献类型：
--
作者：
Paritosh Garg;S. Kale;Lars Rohwedder;O. Svensson
在本文中，我们在输入随机性的背景下研究流和在线算法。对于几个问题，输入序列的随机顺序（与最坏情况的顺序相反）似乎是证明令人满意的保证的必要之害。然而，在这种假设下工作的算法技术往往容易受到分布的微小变化的影响。为此，我们提出了一种新的 emph{对抗性注入} 模型，其中输入是随机排序的，但对手可能会在任意位置注入误导性元素。我们相信，在这种较弱的假设下研究算法可以带来新的见解，特别是更稳健的算法。我们研究了该模型中的两个经典组合优化问题：最大匹配和基数约束单调子模函数最大化。我们的主要技术贡献是针对后者的一种新颖的流算法，该算法计算 0.55 美元的近似值。虽然算法本身干净简单，但相关分析表明，它模拟了输入流的细分，可用于极大地限制对手的能力。
In this paper, we study streaming and online algorithms in the context of randomness in the input. For several problems, a random order of the input sequence---as opposed to the worst-case order---appears to be a necessary evil in order to prove satisfying guarantees. However, algorithmic techniques that work under this assumption tend to be vulnerable to even small changes in the distribution. For this reason, we propose a new emph{adversarial injections} model, in which the input is ordered randomly, but an adversary may inject misleading elements at arbitrary positions. We believe that studying algorithms under this much weaker assumption can lead to new insights and, in particular, more robust algorithms. We investigate two classical combinatorial-optimization problems in this model: Maximum matching and cardinality constrained monotone submodular function maximization. Our main technical contribution is a novel streaming algorithm for the latter that computes a $0.55$-approximation. While the algorithm itself is clean and simple, an involved analysis shows that it emulates a subdivision of the input stream which can be used to greatly limit the power of the adversary.