数据结构与算法

2025年02月 的作者和标题

[1] arXiv:2502.00316 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： Kernighan-Lin 搜索算法 显示英文标题

标题： The Kernighan-Lin Search Algorithm

Ali Dasdan

评论： 20页，12图

主题： 数据结构与算法 (cs.DS)

[2] arXiv:2502.00841 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 多项式时间学习增强算法用于NP难排列问题 显示英文标题

标题： Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems

Evripidis Bampis, Bruno Escoffier, Dimitris Fotakis, Panagiotis Patsilinakos, Michalis Xefteris

主题： 数据结构与算法 (cs.DS)

[3] arXiv:2502.01163 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 有序点集中的最小Riesz s-能量子集选择通过动态规划 显示英文标题

标题： Minimum Riesz s-Energy Subset Selection in Ordered Point Sets via Dynamic Programming

Michael Emmerich

评论： 10页，5图，会议或其他重要信息

主题： 数据结构与算法 (cs.DS)

[4] arXiv:2502.01327 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： IBB：针对长度多样的DNA数据的快速Burrows-Wheeler变换构造 显示英文标题

标题： IBB: Fast Burrows-Wheeler Transform Construction for Length-Diverse DNA Data

Enno Adler, Stefan Böttcher, Rita Hartel, Cederic Alexander Steininger

主题： 数据结构与算法 (cs.DS)

[5] arXiv:2502.01381 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 跨多个图的公平密集子图 显示英文标题

标题： Fair densest subgraph across multiple graphs

Chamalee Wickrama Arachchi, Nikolaj Tatti

主题： 数据结构与算法 (cs.DS)

[6] arXiv:2502.01400 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 公平顶点问题参数化为簇顶点删除 显示英文标题

标题： Fair Vertex Problems Parameterized by Cluster Vertex Deletion

Tomáš Masařík, Jędrzej Olkowski, Anna Zych-Pawlewicz

评论： 23页，1图

主题： 数据结构与算法 (cs.DS) ; 计算复杂性 (cs.CC) ; 计算机科学中的逻辑 (cs.LO)

[7] arXiv:2502.01408 (交叉列表自 cs.DS) [中文pdf, pdf, 其他]

标题： 标签网络中的节点排名 显示英文标题

标题： Node ranking in labeled networks

Chamalee Wickrama Arachchi, Nikolaj Tatti

主题： 数据结构与算法 (cs.DS)

[8] arXiv:2502.01421 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 完全动态的超图谱稀疏化 显示英文标题

标题： Fully Dynamic Spectral Sparsification of Hypergraphs

Gramoz Goranci, Ali Momeni

主题： 数据结构与算法 (cs.DS)

[9] arXiv:2502.01435 (交叉列表自 cs.DS) [中文pdf, pdf, 其他]

标题： 密集子图发现与强三元闭包相结合 显示英文标题

标题： Dense Subgraph Discovery Meets Strong Triadic Closure

Chamalee Wickrama Arachchi, Iiro Kumpulainen, Nikolaj Tatti

主题： 数据结构与算法 (cs.DS)

[10] arXiv:2502.01603 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 西南树：一种用于非交换可逆运算的部分累积的低内存数据结构 显示英文标题

标题： Southwest Tree: A Low-Memory Data Structure for Partial Accumulations by Non-Commutative Invertible Operations

Nicholas J.C. Papadopoulos

评论： 15页，6图，提交至WADS 2025

主题： 数据结构与算法 (cs.DS)

[11] arXiv:2502.02085 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 一种新的拒绝采样方法用于$k$-$\mathtt{means}$++ 以及改进的权衡 显示英文标题

标题： A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs

Poojan Shah, Shashwat Agrawal, Ragesh Jaiswal

主题： 数据结构与算法 (cs.DS) ; 机器学习 (cs.LG)

[12] arXiv:2502.02115 (交叉列表自 cs.DS) [中文pdf, pdf, 其他]

标题： 高效且实用的用于内容流广告的近似算法 显示英文标题

标题： Efficient and Practical Approximation Algorithms for Advertising in Content Feeds

Guangyi Zhang, Ilie Sarpe, Aristides Gionis

评论： 被接受的手稿将发表于TheWebConf 2025

主题： 数据结构与算法 (cs.DS)

[13] arXiv:2502.02193 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 通过放松其参数约束来扩展布隆过滤器的适用性 显示英文标题

标题： Extending the Applicability of Bloom Filters by Relaxing their Parameter Constraints

Paul Walther, Wejdene Mansour, Martin Werner

评论： 18页，7图

主题： 数据结构与算法 (cs.DS)

[14] arXiv:2502.02455 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 关于有序Ruzsa-Szemerédi图的一篇笔记 显示英文标题

标题： A note on Ordered Ruzsa-Szemerédi graphs

Kevin Pratt

主题： 数据结构与算法 (cs.DS) ; 组合数学 (math.CO)

[15] arXiv:2502.02477 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 基于团划分的图压缩算法 显示英文标题

标题： A Clique Partitioning-Based Algorithm for Graph Compression

Akshar Chavan, Sanaz Rabinia, Daniel Grosu, Marco Brocanelli

评论： 14页

主题： 数据结构与算法 (cs.DS)

[16] arXiv:2502.02530 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 最大最小多样化与非对称距离 显示英文标题

标题： Max-Min Diversification with Asymmetric Distances

Iiro Kumpulainen, Florian Adriaens, Nikolaj Tatti

期刊参考： 第30届ACM SIGKDD知识发现与数据挖掘会议论文集。（2024）1440-1450

主题： 数据结构与算法 (cs.DS)

[17] arXiv:2502.02572 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 算法和硬性结果对于$(k,\ell)$-覆盖问题 显示英文标题

标题： Algorithms and Hardness Results for the $(k,\ell)$-Cover Problem

Amirali Madani, Anil Maheshwari, Babak Miraftab, Bodhayan Roy

主题： 数据结构与算法 (cs.DS)

[18] arXiv:2502.02680 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 改进路径上具有释放日期的图旅行商问题的多项式界 显示英文标题

标题： Improving polynomial bounds for the Graphical Traveling Salesman Problem with release dates on paths

Thailsson Clementino, Rosiane de Freitas

主题： 数据结构与算法 (cs.DS)

[19] arXiv:2502.03313 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 近似最优的线性草图和超图谱稀疏化的全动态算法 显示英文标题

标题： Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification

Sanjeev Khanna, Huan Li, Aaron Putterman

主题： 数据结构与算法 (cs.DS)

[20] arXiv:2502.03574 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 带有不准确先验的潘多拉 显示英文标题

标题： Pandora with Inaccurate Priors

Kiarash Banihashem, Xiang Chen, MohammadTaghi Hajiaghayi, Sungchul Kim, Kanak Mahadik, Ryan Rossi, Tong Yu

主题： 数据结构与算法 (cs.DS)

[21] arXiv:2502.03663 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 固定增长图中的快速地理路由 显示英文标题

标题： Fast Geographic Routing in Fixed-Growth Graphs

Ofek Gila, Michael T. Goodrich, Abraham M. Illickan, Vinesh Sridhar

评论： v1将于2025年发表在第14届国际算法与复杂性会议（CIAC'25）上，共26页，5幅图

期刊参考： 讲座笔记 计算科学 15680 (2025) 151-167 讲座笔记 计算科学 15680 (2025) 151-167 讲座笔记 计算科学 15680 (2025) 151-167

主题： 数据结构与算法 (cs.DS)

[22] arXiv:2502.03696 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 级联学习的布隆过滤器用于最优模型-过滤器大小平衡和快速拒绝 显示英文标题

标题： Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection

Atsuki Sato, Yusuke Matsui

主题： 数据结构与算法 (cs.DS) ; 计算复杂性 (cs.CC) ; 机器学习 (cs.LG)

[23] arXiv:2502.03702 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 张量分解与知识编译的结合：一种比较张量列车与OBDDs的研究 显示英文标题

标题： Tensor Decomposition Meets Knowledge Compilation: A Study Comparing Tensor Trains with OBDDs

Ryoma Onaka, Kengo Nakamura, Masaaki Nishino, Norihito Yasuda

主题： 数据结构与算法 (cs.DS)

[24] arXiv:2502.03817 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 知道何时停止很重要：在时间范围不确定性下的在线转换统一算法 显示英文标题

标题： Knowing When to Stop Matters: A Unified Algorithm for Online Conversion under Horizon Uncertainty

Yanzhao Wang, Hasti Nourmohammadi Sigaroudi, Bo Sun, Omid Ardakanian, Xiaoqi Tan

评论： 36页，6图

主题： 数据结构与算法 (cs.DS) ; 机器学习 (cs.LG)

[25] arXiv:2502.04182 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 快速谱内图水印 显示英文标题

标题： Fast In-Spectrum Graph Watermarks

Jade Garcia Bourrée, Anne-Marie Kermarrec, Erwan Le Merrer, Othmane Safsafi

主题： 数据结构与算法 (cs.DS)

[26] arXiv:2502.04632 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 高影响函数、连通性和阈值的噪声计算的紧致界 显示英文标题

标题： Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold

Yuzhou Gu, Xin Li, Yinzhan Xu

评论： 摘要为满足arXiv要求而简化。修正了Ziao Wang指出的开放问题2中的错误。

主题： 数据结构与算法 (cs.DS) ; 计算复杂性 (cs.CC) ; 信息论 (cs.IT)

[27] arXiv:2502.04677 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 基于前缀复用和延迟约束的LLM查询调度 显示英文标题

标题： LLM Query Scheduling with Prefix Reuse and Latency Constraints

Gregory Dexter, Shao Tang, Ata Fatahi Baarzi, Qingquan Song, Tejas Dharamsi, Aman Gupta

主题： 数据结构与算法 (cs.DS)

[28] arXiv:2502.05059 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 距离到唯一顶点覆盖的精确算法 显示英文标题

标题： Exact Algorithms for Distance to Unique Vertex Cover

Foivos Fioravantes, Dušan Knop, Nikolaos Melissinos, Michal Opler, Manolis Vasilakis

主题： 数据结构与算法 (cs.DS) ; 计算复杂性 (cs.CC)

[29] arXiv:2502.05082 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 一种随机化的分布式排序方法 显示英文标题

标题： A Randomised Approach to Distributed Sorting

Sam Olesker-Taylor

评论： 21页：18正文+3附录

主题： 数据结构与算法 (cs.DS) ; 分布式、并行与集群计算 (cs.DC) ; 离散数学 (cs.DM) ; 概率 (math.PR)

[30] arXiv:2502.05373 (交叉列表自 cs.DS) [中文pdf, pdf, 其他]

标题： 算法问题在分划范畴中 显示英文标题

标题： Algorithmic Problems in Categories of Partitions

Nicolas Faroß, Sebastian Volz

评论： 19页

主题： 数据结构与算法 (cs.DS) ; 量子代数 (math.QA)

[31] arXiv:2502.05437 (交叉列表自 cs.DS) [中文pdf, pdf, 其他]

标题： 逼近自旋系统之间的总变差距离 显示英文标题

标题： Approximating the total variation distance between spin systems

Weiming Feng, Hongyang Liu, Minji Yang

评论： 已被COLT 2025接受；修正拼写错误；小修

主题： 数据结构与算法 (cs.DS) ; 机器学习 (cs.LG) ; 概率 (math.PR)

[32] arXiv:2502.05511 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 新的和改进的马尔可夫页面绑定 显示英文标题

标题： New and Improved Bounds for Markov Paging

Chirag Pabbaraju, Ali Vakilian

评论： 26页，3图

主题： 数据结构与算法 (cs.DS)

[33] arXiv:2502.05613 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 结合种子的搜索与编码及其在最小完美哈希中的应用 显示英文标题

标题： Combined Search and Encoding for Seeds, with an Application to Minimal Perfect Hashing

Hans-Peter Lehmann, Peter Sanders, Stefan Walzer, Jonatan Ziegler

主题： 数据结构与算法 (cs.DS)

[34] arXiv:2502.05687 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 近似最优的有向低直径分解 显示英文标题

标题： Near-Optimal Directed Low-Diameter Decompositions

Karl Bringmann, Nick Fischer, Bernhard Haeupler, Rustam Latypov

主题： 数据结构与算法 (cs.DS)

[35] arXiv:2502.05720 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： Pareto-Optimal性，平滑性和学习增强的一最大搜索 显示英文标题

标题： Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search

Ziyad Benomar, Lorenzo Croissant, Vianney Perchet, Spyros Angelopoulos

主题： 数据结构与算法 (cs.DS) ; 人工智能 (cs.AI)

[36] arXiv:2502.05723 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 打破二次障碍：适应性查询的鲁棒基数草图 显示英文标题

标题： Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries

Edith Cohen, Mihir Singhal, Uri Stemmer

主题： 数据结构与算法 (cs.DS)

[37] arXiv:2502.05877 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 无源定向：一种局部采样器及其应用 显示英文标题

标题： Sink-free orientations: a local sampler with applications

Konrad Anand, Graham Freifeld, Heng Guo, Chunyang Wang, Jiaheng Wang

评论： 15页，1图。v2：更新了讨论部分

主题： 数据结构与算法 (cs.DS) ; 离散数学 (cs.DM) ; 概率 (math.PR)

[38] arXiv:2502.05888 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 更快的k-中心问题数据约简近似算法 显示英文标题

标题： Faster Approximation Algorithms for k-Center via Data Reduction

Arnold Filtser, Shaofeng H.-C. Jiang, Yi Li, Anurag Murty Naredla, Ioannis Psarros, Qiaoyuan Yang, Qin Zhang

主题： 数据结构与算法 (cs.DS)

[39] arXiv:2502.05915 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： CDAWGs上的常数灵敏度 显示英文标题

标题： Constant sensitivity on the CDAWGs

Rikuya Hamai, Hiroto Fujimaru, Shunsuke Inenaga

主题： 数据结构与算法 (cs.DS)

[40] arXiv:2502.06024 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 改进的古典和量子图着色的次线性算法 显示英文标题

标题： Improved Sublinear Algorithms for Classical and Quantum Graph Coloring

Asaf Ferber, Liam Hardiman, Xiaonan Chen

主题： 数据结构与算法 (cs.DS)

[41] arXiv:2502.06200 (交叉列表自 cs.DS) [中文pdf, pdf, 其他]

标题： 关于非对数凹分布的采样查询复杂度 显示英文标题

标题： On the query complexity of sampling from non-log-concave distributions

Yuchen He, Chihao Zhang

评论： 论文的扩展摘要将在COLT 2025上展示。

主题： 数据结构与算法 (cs.DS) ; 机器学习 (cs.LG) ; 机器学习 (stat.ML)

[42] arXiv:2502.06459 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 最大覆盖$k$-反链和链：一种贪心方法 显示英文标题

标题： Maximum Coverage $k$-Antichains and Chains: A Greedy Approach

Manuel Cáceres, Andreas Grigorjew, Wanchote Po Jiamjitrak, Alexandru I. Tomescu

主题： 数据结构与算法 (cs.DS)

[43] arXiv:2502.06461 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 新的针对相等关键字的简单快速排序算法 显示英文标题

标题： New simple and fast quicksort algorithm for equal keys

Parviz Afereidoon

评论： 8页，5图

主题： 数据结构与算法 (cs.DS)

[44] arXiv:2502.06477 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 到达：递归框架与$\ell_1$-收缩 显示英文标题

标题： ARRIVAL: Recursive Framework & $\ell_1$-Contraction

Sebastian Haslebacher

评论： 18页

主题： 数据结构与算法 (cs.DS)

[45] arXiv:2502.06522 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 近似算法用于最优跳集 显示英文标题

标题： Approximation Algorithms for Optimal Hopsets

Michael Dinitz, Ama Koranteng, Yasamin Nazari

评论： 30页，0图。发表于ICALP 2025

主题： 数据结构与算法 (cs.DS) ; 离散数学 (cs.DM)

[46] arXiv:2502.06558 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 关于在线单位区间着色的FirstFit算法 显示英文标题

标题： On the FirstFit Algorithm for Online Unit-Interval Coloring

Bob Krekelberg, Alison Hsiang-Hsuan Liu

评论： 24页，5图

主题： 数据结构与算法 (cs.DS)

[47] arXiv:2502.06564 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 接近最优的鲁棒协方差和散度矩阵估计超越高斯分布 显示英文标题

标题： Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians

Gleb Novikov

主题： 数据结构与算法 (cs.DS) ; 机器学习 (cs.LG) ; 统计理论 (math.ST) ; 机器学习 (stat.ML)

[48] arXiv:2502.06586 (交叉列表自 cs.DS) [中文pdf, pdf, 其他]

标题： 当$q>3Δ$时，边着色的相关性衰减 显示英文标题

标题： Decay of correlation for edge colorings when $q>3Δ$

Zejia Chen, Yulin Wang, Chihao Zhang, Zihan Zhang

评论： 已被ICALP 2025接受

主题： 数据结构与算法 (cs.DS) ; 概率 (math.PR)

[49] arXiv:2502.06730 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 工程视角下的双克利分割与矩阵的分数二进制秩 显示英文标题

标题： Engineering Insights into Biclique Partitions and Fractional Binary Ranks of Matrices

Angikar Ghosal, Andreas Karrenbauer

主题： 数据结构与算法 (cs.DS)

[50] arXiv:2502.07062 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 突破界限：具有次线性适应性的非单调子模最大化组合算法与$1/e$逼近 显示英文标题

标题： Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation

Yixin Chen, Wenjing Chen, Alan Kuhnle

主题： 数据结构与算法 (cs.DS)