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

DOI10.1007/s10107-021-01625-2zbMath1494.90096arXiv2003.02424OpenAlexW3010015543MaRDI QIDQ5918723

Yuni Iwamasa, Kenjiro Takazawa

Publication date: 29 June 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2003.02424

zbMATH Keywords

congestion gamecombinatorial optimization problem with interaction costsM-convex submodular flowvaluated independent assignmentvaluated matroid intersectionrecoverable robust matroid basis problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Min-max-min robust combinatorial optimization
• Convexity and Steinitz's exchange property
• Valuated matroids: A new look at the greedy algorithm
• Submodular flow problem with a nonseparable cost function
• Valuated matroids
• Discrete convex analysis
• A capacity scaling algorithm for M-convex submodular flow
• Potential games
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial optimization with interaction costs: complexity and solvable cases
• The recoverable robust spanning tree problem with interval costs is polynomially solvable
• Recoverable robust spanning tree problem under interval uncertainty representations
• A class of games possessing pure-strategy Nash equilibria
• Submodular functions and optimization.
• On the complexity of min-max-min robustness with two alternatives and budgeted uncertainty
• M-Convex Function on Generalized Polymatroid
• Recent Developments in Discrete Convex Analysis
• On the impact of combinatorial structure on congestion games
• Minimum cost flow with set-constraints
• A weighted matroid intersection algorithm
• Computing Maximal “Polymatroidal” Network Flows
• Matroid intersection algorithms
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• Discrete Convex Analysis
• Sensitivity Analysis for Convex Separable Optimization Over Integral Polymatroids
• Valuated Matroid Intersection I: Optimality Criteria
• Valuated Matroid Intersection II: Algorithms
• Flow Network Formulations of Polymatroid Optimization Problems
• Conjugate Scaling Algorithm for Fenchel-Type Duality in Discrete Convex Optimization
• Recoverable Robust Combinatorial Optimization Problems
• Fibonacci heaps and their uses in improved network optimization algorithms
• Finding minimum congestion spanning trees
• Matrices and matroids for systems analysis
• Generalizations of weighted matroid congestion games: pure Nash equilibrium, sensitivity analysis, and discrete convex function

This page was built for publication: Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications