Coordinatewise domain scaling algorithm for M-convex function minimization
From MaRDI portal
Publication:1771308
DOI10.1007/s10107-004-0522-yzbMath1079.90118OpenAlexW2157867221MaRDI QIDQ1771308
Publication date: 19 April 2005
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-004-0522-y
discrete optimizationDiscrete convex analysisM-convex function minimizationnonlinear discrete functionsScaling algorithm
Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Related Items
M-Convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Reallocation in Bike-Sharing System, Scaling, proximity, and optimization of integrally convex functions, Recent Developments in Discrete Convex Analysis, Congestion games viewed from M-convexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Convexity and Steinitz's exchange property
- Valuated matroids: A new look at the greedy algorithm
- Generalized polymatroids and submodular flows
- Submodular flow problem with a nonseparable cost function
- Two algorithms for maximizing a separable concave function over a polymatroid feasible region
- Submodular functions and optimization
- Valuated matroids
- Discrete convex analysis
- Minimization of an M-convex function
- Gross substitution, discrete convexity, and submodularity
- Quasi M-convex and L-convex functions -- quasiconvexity in discrete optimization
- New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities.
- Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
- Application of M-convex submodular flow problem to mathematical economics
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A fully combinatorial algorithm for submodular function minimization.
- Combinatorial auctions with decreasing marginal utilities
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- A Primal-Dual Algorithm for Submodular Flows
- Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
- Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
- Discrete Convex Analysis
- Conjugate Scaling Algorithm for Fenchel-Type Duality in Discrete Convex Optimization
- Convex Analysis
- A Note on Kelso and Crawford's Gross Substitutes Condition
- Matrices and matroids for systems analysis
- Discrete convexity and equilibria in economies with indivisible goods and money
