M-convex function minimization by continuous relaxation approach: proximity theorem and algorithm

DOI10.1137/080736156MaRDI QIDQ3105769zbMATH OpenOpenAlexFDO

Authors Satoko Moriguchi, Akiyoshi Shioura, Nobuyuki Tsuchimura

Publication date 9 January 2012

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/cf6d768849db2f0bfb4b05e49e22876c364195d3

zbMATH Keywords

convex functiondiscrete optimizationmatroidsubmodular function

Mathematics Subject Classification ID

Integer programming (90C10) Convex programming (90C25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Discrete L-convex function minimization based on continuous relaxation
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
• Submodular function minimization and maximization in discrete convex analysis
• Conjugate Scaling Algorithm for Fenchel-Type Duality in Discrete Convex Optimization

Cited in

(17)

• Minimization of an M-convex function
• Algorithms for separable convex optimization with linear ascending constraints
• Simpler exchange axioms for M-concave functions on generalized polymatroids
• Continuous relaxation for discrete DC programming
• Decreasing minimization on M-convex sets: algorithms and applications
• Decreasing minimization on base-polyhedra: relation between discrete and continuous cases
• Scaling, proximity, and optimization of integrally convex functions
• Minimizing continuous extensions of discrete convex functions with linear inequality constraints
• Discrete L-convex function minimization based on continuous relaxation
• Sensitivity analysis for convex separable optimization over integral polymatroids
• scientific article; zbMATH DE number 2086911 (Why is no real title available?)
• Time bounds of basic steepest descent algorithms for \(M\)-convex function minimization and related problems
• M-Convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Reallocation in Bike-Sharing System
• On a Reduction for a Class of Resource Allocation Problems
• Continuous relaxation for discrete DC programming
• Generalizations of weighted matroid congestion games: pure Nash equilibrium, sensitivity analysis, and discrete convex function
• Note on Minimization of Quasi M^\natural-convex Functions

This page was built for publication: M-convex function minimization by continuous relaxation approach: proximity theorem and algorithm

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