.png){kind=icon}
返回
Unit Interval Selection in Random Order Streams
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.STACS.2026.4.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们考虑在单次随机顺序流模型中的单位区间选择问题。在此设置中，算法被呈现一个线上的n个单位长度区间的序列，这些区间以均匀随机顺序逐个到达，目标是输出（最优解的近似）一个最大的不相交区间集，使用的空间与最优解的大小呈线性关系。先前的工作仅考虑了恶意排序的流，并确立了在这些空间约束下，可以在这样的流中实现(2/3)-近似，这是最佳可能的，因为超越此近似因子需要Ω(n)空间[Emek等人，TALG'16]。在本工作中，我们表明，如果输入流是均匀随机顺序，则可以实现改进的期望近似因子，其中期望是基于流顺序的。更具体地说，我们给出一个单次流算法，其期望近似因子为0.7401，使用的空间为O(|OPT|)，其中OPT表示最优解。我们还表明，期望近似因子高于8/9的随机顺序算法需要Ω(n)空间，且以高于2/3的概率计算优于2/3-近似的算法也需要Ω(n)空间。在技术层面，我们为受限域[0,Δ)设计了一个算法，其中Δ为某个常数，并使用标准技术获得无限制域的算法。对于受限域[0,Δ)，我们运行O(Δ)个递归实例的算法，每个实例针对最优解的一个特定区间首先到达的情况。我们确立了算法的一个有趣性质：当输入流仅由一组独立区间组成时，算法表现最差。然后需要分析算法在这些简单实例上的性能。我们的下界是通过通信复杂度论证证明的，其精神类似于[Chakrabarti等人，Theory Comput. 2016]建立的鲁棒通信下界。
Keyword:
Random order streaming algorithms
unit interval selection
期刊
机构
引用论文
暂无论文信息