Minimization of an M-convex function

DOI10.1016/S0166-218X(97)00140-6zbMath0902.90133MaRDI QIDQ1392577

Akiyoshi Shioura

Publication date: 18 October 1998

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

convex functionminimizationmatroidbase polyhedron

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

Supermodular functions and the complexity of MAX CSP, M-Convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Reallocation in Bike-Sharing System, Every finite distributive lattice is isomorphic to the minimizer set of an \(M^\natural \)-concave set function, 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., Coordinatewise domain scaling algorithm for M-convex function minimization, Congestion games viewed from M-convexity, Discrete convex analysis, Extension of M-convexity and L-convexity to polyhedral convex functions

Cites Work

• Convexity and Steinitz's exchange property
• Valuated matroids: A new look at the greedy algorithm
• 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
• Geometric algorithms and combinatorial optimization
• 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