English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

For two matroids $M_1$ and $M_2$ with the same ground set $V$ and two costfunctions $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 acertain cardinality constraint on their intersection $X_1 \cap X_2$. For thisproblem, Lendl, Peis, and Timmermans (2019) discussed modular cost functions:they reduced the problem to weighted matroid intersection for the case wherethe 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 convexcost functions, and to comprehend them from the viewpoint of discrete convexanalysis. We prove that each generalized problem can be solved via valuatedindependent assignment, valuated matroid intersection, or $\mathrm{M}$-convexsubmodular flow, to offer a comprehensive understanding of weighted matroidintersection with intersection constraints. We also show the NP-hardness ofsome variants of these problems, which clarifies the coverage of discreteconvex analysis for those problems. Finally, we present applications of ourgeneralized problems in the recoverable robust matroid basis problem,combinatorial optimization problems with interaction costs, and matroidcongestion games.

Optimal matroid bases with intersection constraints: Valuated matroids, M-convex functions, and their applications