Equivalence of convex minimization problems over base polytopes

DOI10.1007/s13160-012-0083-zzbMath1254.90168OpenAlexW2088408727MaRDI QIDQ1926652

Kiyohito Nagano, Kazuyuki Aihara

Publication date: 28 December 2012

Published in: Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s13160-012-0083-z

zbMATH Keywords

convex optimizationcombinatorial optimizationsubmodular function

Mathematics Subject Classification ID

Convex programming (90C25) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial optimization (90C27)

Related Items

On a Reduction for a Class of Resource Allocation Problems ⋮ A fast algorithm for quadratic resource allocation problems with nested constraints ⋮ Lexicographically optimal earliest arrival flows ⋮ Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The egalitarian solution and reduced game properties in convex games
• Submodular function minimization
• A faster strongly polynomial time algorithm for submodular function minimization
• Two algorithms for maximizing a separable concave function over a polymatroid feasible region
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A strongly polynomial algorithm for line search in submodular polyhedra
• Submodular functions and optimization.
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• A Concept of Egalitarianism Under Participation Constraints
• Submodular systems and related topics
• NOTE ON THE UNIVERSAL BASES OF A PAIR OF POLYMATROIDS
• Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
• Optimal flows in networks with multiple sources and sinks
• Finding the nearest point in A polytope
• Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
• A Fast Parametric Maximum Flow Algorithm and Applications
• Submodular Function Minimization under Covering Constraints

This page was built for publication: Equivalence of convex minimization problems over base polytopes