Approximation Algorithms for the -Matching and List-Restricted Variants of MaxQAP
本文针对最大二次分配问题（MaxQAP）的两种自然推广形式——列表限制变体和 -匹配变体，分别设计了基于线性规划松弛与随机舍入的 和 近似算法，并在特定条件下实现了与 MaxQAP 最佳已知近似因子渐近匹配的首个近似解。
💻 Category
cs.DM
48 篇论文
Robust Permutation Flowshops Under Budgeted Uncertainty
本文证明了在预算不确定性模型下，鲁棒置换流水车间问题可通过求解多项式个名义问题实例来解决，从而得出该问题在双机情况下可多项式时间求解、在任意固定机器数下可多项式时间近似求解的结论，并提供了针对双机和三机情形的运行时间对数级改进。
Positional s-of-k games
本文提出了名为"s-of-k 游戏”的通用位置博弈框架，通过设定阈值将得分条件扩展为“至少占据元获胜集合中的个元素”，并针对三角、正方形、菱形和六边形网格，在最优策略与配对策略限制下对 Maker 的得分进行了全面分析与界值估计。
Minimal toughness in subclasses of weakly chordal graphs
本文研究了弱弦图子类中最小坚韧图的结构，并完成了对补弦图（其补图直径至少为 3）、无网补弦图、森林的补图、-free 图以及完全多部图这几类子图的完整分类，同时为相关已知结果提供了简洁证明。
Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees
本文研究了凸位置点集上平面生成树的最短翻转序列的结构性质，验证并反驳了关于“幸福边”、“停车边”及“重复停车”的三个相关猜想，揭示了这些猜想仅在特定条件下成立而在一般情形下不成立。
Algebraic Characterization of Reversible First Degree Cellular Automata over
本文针对有限元胞自动机，通过建立仅含三个代数条件的充要判据，实现了在常数时间内对任意规模一维三邻域态一阶元胞自动机可逆性的判定与规则合成。
ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
该论文提出了一种针对有界树宽复形上最优莫尔斯匹配问题的 $2^{O(k \log k)} n2^{o(k \log k)} n^{O(1)}$ 时间的算法，从而确定了该问题关于树宽参数的紧确复杂度。
Submodular Maximization over a Matroid -Intersection: Multiplicative Improvement over Greedy
本文提出了一种针对受 个任意拟阵交约束的非负单调子模函数最大化问题的新算法，该算法实现了优于传统贪心算法的 $0.819k+O(\sqrt{k})kk$ 无关。