针对超大规模优化问题，提出高效剪枝算法快速去除冗余元素。
Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization
- 基于理论保证设计轻量剪枝算法，可快速剔除非最优候选元素。
- 在真实数据集上剪枝超90%元素，且保留最优解价值比例高。
- 适合处理海量规模的组合优化问题，尤其适用于工业级应用。
现代组合优化问题常涉及百亿量级的候选元素集合，其中包含大量无信息或冗余项。本文提出轻量级剪枝算法QuickPrune，可在温和假设下理论上保证剪枝后仍保留大部分最优值，并显著缩小问题规模。在多种真实应用场景的数据集上进行的大量实验表明，该方法能高效剪除超过90%的元素，优于现有经典及机器学习类剪枝启发式算法。
原文摘要 · Abstract (English)
Modern instances of combinatorial optimization problems often exhibit billion-scale ground sets, which have many uninformative or redundant elements. In this work, we develop light-weight pruning algorithms to quickly discard elements that are unlikely to be part of an optimal solution. Under mild assumptions on the instance, we prove theoretical guarantees on the fraction of the optimal value retained and the size of the resulting pruned ground set. Through extensive experiments on real-world datasets for various applications, we demonstrate that our algorithm, QuickPrune, efficiently prunes over 90% of the ground set and outperforms state-of-the-art classical and machine learning heuristics for pruning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。