我们研究了在 $k$ 个矩阵交集中的最大值集合的寻找问题，给定一个单调次模函数。我们的主要结果是一个多项式时间的局部搜索算法，能够实现 $\frac{k}{2} + o(k)$ 的近似保证。这与 Lee、Sviridenko 和 Vondrák（2009）在无权情况下的最佳已知保证 $\frac{k}{2} + \epsilon$ 逐渐匹配。
在此之前，最先进的算法是 Feldman 和 Ward（2026）提出的 $\frac{\ln(4)k}{1+\ln(2)} + o(k)$ 近似算法。我们的算法还扩展到矩阵 $k$-Parity，获得相同的近似保证。
与 Singer 和 Thiery（2025）以及 Feldman 和 Ward（2026）所采用的权重分桶方法不同，我们的算法贪婪地处理元素，以边际值递减的顺序进行搜索，寻找收益超过参数 $\alpha$（作为 $k$ 的函数）的足够有利的交换。我们进一步将这一思路与权重分桶方法结合，以获得加权 $k$-集合打包问题的改进保证。
我们的第二个主要结果是一个 $\frac{\ln(4)k}{3} + o(k)$ 的加权 $k$-集合打包的近似算法，优于 Neuwohner（2023）提出的 $\frac{k}{2.00561} + O(1)$ 的最先进近似。
博主点评： 本文提出的算法在多重矩阵下的次模最大化问题上实现了新的近似保证，显示出局部搜索策略的有效性，尤其是在处理复杂的组合优化问题时。与现有方法相比，结合贪婪策略与权重分桶的创新思路，为未来的研究提供了新的方向。