Exact bounds for steepest descent algorithms of $L$-convex function minimization

DOI10.1016/j.orl.2014.06.005zbMath1408.90261OpenAlexW2048844673MaRDI QIDQ1785253

Kazuo Murota, Akiyoshi Shioura

Publication date: 28 September 2018

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

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

zbMATH Keywords

steepest descent algorithmdiscrete optimizationanalysis of algorithmdiscrete convex function

Mathematics Subject Classification ID

Convex programming (90C25) Combinatorial optimization (90C27) Axiomatic and generalized convexity (52A01)

Related Items

Note on time bounds of two-phase algorithms for \(L\)-convex function minimization, Discrete Midpoint Convexity, Geodesic property of greedy algorithms for optimization problems on jump systems and delta-matroids, L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem, Time bounds for iterative auctions: a unified approach by discrete convex analysis, Robust budget allocation via continuous submodular functions, Directed discrete midpoint convexity, Discrete Convex Functions on Graphs and Their Algorithmic Applications, Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings

Cites Work

• Unnamed Item
• Unnamed Item
• New algorithms for convex cost tension problem with application to computer vision
• A dual algorithm for submodular flow problems
• The English auction with differentiated commodities
• Dijkstra's algorithm and L-concave function maximization
• Image restoration with discrete constrained total variation. I: Fast and exact optimization
• Computing a Walrasian Equilibrium in Iterative Auctions with Multiple Differentiated Items
• On the Optimal Policy Structure in Serial Inventory Systems with Lost Sales
• On the Structure of Lost-Sales Inventory Models
• Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
• The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm
• Job Matching, Coalition Formation, and Gross Substitutes
• Discrete Convex Analysis
• On Steepest Descent Algorithms for Discrete Convex Functions