Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.

DOI10.1016/S0166-218X(03)00255-5zbMath1038.90059MaRDI QIDQ1421475

Akiyoshi Shioura

Publication date: 26 January 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

Resource allocationBase polyhedronMinimizationDiscrete optimizationConvex function

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

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, Simpler exchange axioms for M-concave functions on generalized polymatroids, Buyback problem with discrete concave valuation functions, Applications of discrete convex analysis to mathematical economics, Coordinatewise domain scaling algorithm for M-convex function minimization, A capacity scaling algorithm for M-convex submodular flow, Congestion games viewed from M-convexity, ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS, Competitive Equilibrium and Trading Networks: A Network Flow Approach

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Convexity and Steinitz's exchange property
• Valuated matroids: A new look at the greedy algorithm
• Two algorithms for maximizing a separable concave function over a polymatroid feasible region
• Valuated matroids
• Geometric algorithms and combinatorial optimization
• Discrete convex analysis
• Minimization of an M-convex function
• Quasi M-convex and L-convex functions -- quasiconvexity in discrete optimization
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Submodular functions and optimization.
• M-Convex Function on Generalized Polymatroid
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for Optimality
• Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
• Discrete Convex Analysis
• On Steepest Descent Algorithms for Discrete Convex Functions
• On Minimizing Nonseparable Functions Defined on the Integers with an Inventory Application
• A polynomial algorithm for resourse allocation problems with polymatroid constrains¹
• On Hochbaum's Proximity-Scaling Algorithm for the General Resource Allocation Problem