An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint

DOI10.1016/j.orl.2023.01.003zbMath1525.90373OpenAlexW4315476327MaRDI QIDQ6161898

Kenjiro Takazawa

Publication date: 28 June 2023

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2023.01.003

zbMATH Keywords

polynomial algorithmmatroid intersectiongeneralized polymatroidnonseparable discrete convex function

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Convexity and Steinitz's exchange property
• A note on Frank's generalized polymatroids
• Matroid optimization with the interleaving of two ordered sets
• Submodular flow problem with a nonseparable cost function
• Linear multiplicative programming
• Discrete convex analysis
• Optimization on low rank nonconvex structures
• Application of M-convex submodular flow problem to mathematical economics
• Optimization problems with color-induced budget constraints
• The quadratic minimum spanning tree problem and its variations
• The quadratic M-convexity testing problem
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• A capacity scaling algorithm for M-convex submodular flow
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Quadratic M-convex and L-convex functions
• Submodular functions and optimization.
• M-Convex Function on Generalized Polymatroid
• Efficient algorithms for a family of matroid intersection problems
• Discrete Convex Analysis
• Valuated Matroid Intersection II: Algorithms
• Conjugate Scaling Algorithm for Fenchel-Type Duality in Discrete Convex Optimization

This page was built for publication: An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint