|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Optimal matroid bases with intersection constraints: Valuated matroids, M-convex functions, and their applications | | Yuni Iwamasa
; Kenjiro Takazawa
; | | Date: |
5 Mar 2020 | | Abstract: | 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$. 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, matroid
congestion games, and combinatorial optimization problems with interaction
costs. | | Source: | arXiv, 2003.2424 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER