论文标题
与交点约束的最佳矩阵基础：有价值的矩阵，M-Convex函数及其应用
Optimal matroid bases with intersection constraints: Valuated matroids, M-convex functions, and their applications
论文作者
论文摘要
对于两个具有相同地面套装$ v $的$ m_1 $和$ m_2 $的$ m_1 $和$ m_2 $，两个成本函数$ w_1 $和$ w_2 $ 2^v $上的$ w_2 $，我们考虑找到bases $ x_1 $ x_1 $ $ x_1 $的$ m_1 $和$ x_2 $的$ x_2 $ of $ m_2 $ $ m_2 $最小化$ w_1（x_1）$ w_1（x_1）+w_1（x_1）+w_2（x_2）$ w_2（x_2） $ x_1 \ cap x_2 $。对于这个问题，Lendl，Peis和Timmermans（2019）讨论了模块化成本功能：对于基数约束为$ | x_1 \ cap x_2 | \ cap x_2 | \ le k $或$ | x_1 \ x_1 \ x_1 \ cap x_2 | x_2 | \ ge k $;并为约束为$ | x_1 \ cap x_2 | = k $的情况设计了一种新的原始双算法。 本文的目的是概括具有非线性凸成本函数的问题，并从离散凸分析的角度理解它们。我们证明，每个广义问题都可以通过有价值的独立分配，有价值的Matroid交叉点或$ \ MathRM {M} $ - 凸出的下管流，以便对加权的Matroid与交叉点约束的重量相交进行全面的了解。我们还显示了这些问题的某些变体的NP硬度，这阐明了这些问题的离散凸分析的覆盖范围。最后，我们在可回收的鲁棒矩阵基础问题，互动成本和矩阵拥堵游戏中提出了广义问题的应用。
For two matroids $M_1$ and $M_2$ with the same ground set $V$ and two cost functions $w_1$ and $w_2$ on $2^V$, we consider the problem of finding bases $X_1$ of $M_1$ and $X_2$ of $M_2$ minimizing $w_1(X_1)+w_2(X_2)$ subject to a certain cardinality constraint on their intersection $X_1 \cap X_2$. For this problem, Lendl, Peis, and Timmermans (2019) discussed modular cost functions: they reduced the problem to weighted matroid intersection for the case where the cardinality constraint is $|X_1 \cap X_2|\le k$ or $|X_1 \cap X_2|\ge k$; and designed a new primal-dual algorithm for the case where the constraint is $|X_1 \cap X_2|=k$. The aim of this paper is to generalize the problems to have nonlinear convex cost functions, and to comprehend them from the viewpoint of discrete convex analysis. We prove that each generalized problem can be solved via valuated independent assignment, valuated matroid intersection, or $\mathrm{M}$-convex submodular flow, to offer a comprehensive understanding of weighted matroid intersection with intersection constraints. We also show the NP-hardness of some variants of these problems, which clarifies the coverage of discrete convex analysis for those problems. Finally, we present applications of our generalized problems in the recoverable robust matroid basis problem, combinatorial optimization problems with interaction costs, and matroid congestion games.
