Concurrent Deterministic Skiplist and Other Data Structures
本文设计并评估了一种适用于多核 NUMA 架构的并发确定性跳表，同时对比了无锁队列与哈希表实现的性能，提出了优化内存管理的策略，并建议通过分层使用并发数据结构来减少远程节点访问以降低内存延迟。
💻 Category
cs.DS
87 篇论文
Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
本文证明了对于任意固定图，最大部分列表-着色问题在-自由图上可在多项式时间内求解，从而解决了 Agrawal 等人提出的开放问题，并将 Chudnovsky 等人之前的算法复杂度从改进为多项式时间。
Differentially Private and Scalable Estimation of the Network Principal Component
本文提出了一种基于“提议 - 测试 - 发布”（PTR）框架的可扩展差分隐私算法，通过实例特定机制在保持隐私的同时显著降低噪声并提升计算效率，实现了在大规模真实网络中高效且准确地估计网络主成分及求解最密-子图问题。
Bounds for the Permutation Flowshop Scheduling Problem: New Framework and Theoretical Insights
本文提出了一种基于矩阵表述和路径集极值求解的通用框架，用于推导置换流水车间调度问题的上下界，该框架在多项式时间内显著提升了 Taillard 和 VRF 基准测试集上的界限精度，并进一步改进了关于下界质量及算法渐近近似比的理论猜想。
No exponential quantum speedup for anymore
本文针对 Chen、Liu 和 Zhandry 于 2021 年提出的平均情况 -短整数解（）问题的量子加速算法，提出了针对该问题及更广义约束整数解问题的有效经典算法，从而证明不再存在指数级量子加速。
An Algorithm for Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
本文针对具有单断点全单位折扣且采购价格非递增的单物品批量问题，通过建立最优解的新性质并设计一种混合动态规划算法，将求解时间复杂度从现有的降低至。
Towards an algebraic approach to the reconfiguration CSP
本文提出了一种受经典 CSP 复杂性分析启发的新型代数方法，通过利用部分运算而非全运算来处理等式约束，从而将布尔域上的重配置 CSP 复杂性二分结果推广至更通用的场景。
Approximation Algorithms for the -Matching and List-Restricted Variants of MaxQAP
本文针对最大二次分配问题（MaxQAP）的两种自然推广形式——列表限制变体和 -匹配变体，分别设计了基于线性规划松弛与随机舍入的 和 近似算法，并在特定条件下实现了与 MaxQAP 最佳已知近似因子渐近匹配的首个近似解。
Robust Permutation Flowshops Under Budgeted Uncertainty
本文证明了在预算不确定性模型下，鲁棒置换流水车间问题可通过求解多项式个名义问题实例来解决，从而得出该问题在双机情况下可多项式时间求解、在任意固定机器数下可多项式时间近似求解的结论，并提供了针对双机和三机情形的运行时间对数级改进。
Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions
本文提出了一种利用辅助预测信息来增强分布独立性检验的框架，该框架在确保最坏情况下有效性的同时，能够根据预测质量自适应地降低样本复杂度，并证明了其样本复杂度的最优性。
Generalizing Fair Top- Selection: An Integrative Approach
本文针对多保护组下的公平 Top- 选择问题，揭示了现有假设下的计算不可行性并提出了针对小规模 的高效算法，同时引入效用损失作为新的差异度量以增强评分函数的稳定性，最终通过工程权衡在真实数据集上实现了优异性能。
Quantum Algorithms for Network Signal Coordination
本文提出并验证了用于解决 NP 完全网络信号协调（NSC）问题及其鲁棒变体的量子算法，通过格罗弗搜索实现了二次加速，并证明了该算法在多项式精度鲁棒性下仍能保持与搜索空间规模无关的二次量子加速优势。
Revisiting Graph Modification via Disk Scaling: From One Radius to Interval-Based Radii
本文将单位圆盘图的几何修改操作从固定半径缩放推广至区间半径缩放，证明了该问题在多项式可识别图类中属于 XP 类，并针对团图、完全图和连通图分别给出了 NP 难且 FPT、多项式时间可解以及 W[1]-难的复杂性分类结果，从而回答了 Fomin 等人提出的开放问题并推广了相关硬度结论。
Generalized matching decoders for 2D topological translationally-invariant codes
本文提出了一种针对二维拓扑平移不变量子码的广义图匹配解码方法，通过将码字粗粒化为等效的环面码激发态来证明其具备理论纠错能力，并验证了其在双变量自行车码等实际代码上的优异性能。
ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
该论文提出了一种针对有界树宽复形上最优莫尔斯匹配问题的 $2^{O(k \log k)} n2^{o(k \log k)} n^{O(1)}$ 时间的算法，从而确定了该问题关于树宽参数的紧确复杂度。
Finding Short Paths on Simple Polytopes
该论文证明了在简单多胞体上计算线性规划的最短单调路径及单纯形法的最短枢轴序列是 NP 难的（从而解决了两个长期开放问题），并指出即使在分数背包多胞体上该问题依然困难，同时提出了可在多项式时间内找到任意顶点对间线性长度路径的小规模简单扩展形式这一正面结果。
Dynamic Kernel Graph Sparsifiers
本文提出了一种完全动态的数据结构，能够在点集位置发生单点更新时，以 的更新时间和 的初始化时间高效维护几何图的光谱稀疏子图，并支持对抗性环境及相关的矩阵向量运算。
An Objective Improvement Approach to Solving Discounted Payoff Games
该论文提出了一种全新的对称方法，通过构建包含所有边的约束系统并最小化不等式误差之和，以逐步改进的方式求解折扣收益博弈，从而打破了此类问题求解仅依赖策略改进或值迭代方法的传统认知。
A computational transition for detecting correlated stochastic block models by low-degree polynomials
本文研究了从具有 个对称社区的稀疏随机块模型中采样得到的成对相关图与独立 Erdős-Rényi 图之间的相关性检测问题，确定了基于邻接矩阵低阶多项式的检测阈值，证明当且仅当子采样概率 超过 Otter 常数 与 Kesten-Stigum 阈值 中的较小值时，该类检测才是可行的。
Highway Dimension: a Metric View
本文通过放宽高速公路维度的定义以涵盖所有倍增空间（如网格图和欧几里得平面），构建了相应的度量工具包，并在此新定义下为旅行商问题（TSP）设计了多项式时间近似方案（PTAS）。