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

DOI10.1016/J.ORL.2023.01.003MaRDI QIDQ6161898zbMATH OpenOpenAlexFDO

Authors 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

generalized polymatroidmatroid intersectionnonseparable discrete convex functionpolynomial algorithm

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1377657
• Minimization of an M-convex function
• Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
• Coordinatewise domain scaling algorithm for M-convex function minimization
• Optimization problems with color-induced budget constraints

Cites work

• \(M\)-convex function on generalized polymatroid
• A capacity scaling algorithm for M-convex submodular flow
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• A note on Frank's generalized polymatroids
• Application of M-convex submodular flow problem to mathematical economics
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Conjugate Scaling Algorithm for Fenchel-Type Duality in Discrete Convex Optimization
• Convexity and Steinitz's exchange property
• Discrete Convex Analysis
• Discrete convex analysis
• Efficient algorithms for a family of matroid intersection problems
• scientific article; zbMATH DE number 3862931 (Why is no real title available?)
• scientific article; zbMATH DE number 3906513 (Why is no real title available?)
• scientific article; zbMATH DE number 35513 (Why is no real title available?)
• scientific article; zbMATH DE number 757680 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Linear multiplicative programming
• Matroid optimization with the interleaving of two ordered sets
• Optimization on low rank nonconvex structures
• Optimization problems with color-induced budget constraints
• Quadratic M-convex and L-convex functions
• Submodular flow problem with a nonseparable cost function
• Submodular functions and optimization.
• The quadratic M-convexity testing problem
• The quadratic minimum spanning tree problem and its variations
• Valuated Matroid Intersection II: Algorithms

Cited in

(1)

• Steepest descent algorithm for M-convex function minimization using long step length

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6161898)