Optimal matroid bases with intersection constraints: Valuated matroids, M-convex functions, and their applications
Optimal matroid bases with intersection constraints: Valuated matroids, M-convex functions, and their applications
复制标题
具有交集约束的最优拟阵基：评估拟阵、M-凸函数及其应用
DOI：
10.1007/s10107-021-01625-2
复制
发表时间：
2021
影响因子：
2.7
通讯作者：
Kenjiro Takazawa
中科院分区：
文献类型：
--
作者：
Yuni Iwamasa;Kenjiro Takazawa
对于具有相同基集V和两个代价函数的两个拟阵，我们考虑了在它们的交集上满足一定的基数约束的求基和最小化的问题。Lendl，Peis和Timmermann(2019)讨论了模代价函数：对于基数约束为OR的情况，他们将问题归结为加权拟阵交集；对于其中的情况，他们设计了一个新的原始-对偶算法。本文的目的是将具有非线性凸代价函数的问题进行推广，并从离散凸分析的角度来理解它们。我们证明了每个广义问题都可以通过赋值独立分配、赋值拟阵交或-凸子模流来求解，从而提供了对带交约束的加权拟阵交的全面理解。我们还证明了这些问题的一些变种的NP-难性质，从而阐明了离散凸分析对这些问题的覆盖范围。最后，我们给出了我们的广义问题在拟阵拥塞对策和带交互费用的组合优化问题中的应用。
For two matroidsandwith the same ground setVand two cost functionsandon, we consider the problem of finding basesofandofminimizingsubject to a certain cardinality constraint on their intersection. Lendl, Peis, and Timmermans (2019) discussed modular cost functions: They reduced the problem to weighted matroid intersection for the case where the cardinality constraint isor; and designed a new primal-dual algorithm for the case where. 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-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 matroid congestion games and combinatorial optimization problems with interaction costs.