Two algorithms for maximizing a separable concave function over a polymatroid feasible region

90C25: Convex programming

90C60: Abstract computational complexity for mathematical programming problems

91B32: Resource and cost allocation (including fair division, apportionment, etc.)

90-08: Computational methods for problems pertaining to operations research and mathematical programming

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
The complexity of selection and ranking in X+Y and matrices with sorted columns
The ellipsoid method and its consequences in combinatorial optimization
Adjacency on polymatroids
The Partial Order of a Polymatroid Extreme Point
Establishing Consistent and Realistic Reorder Intervals in Production-Distribution Systems
Optimal Flows in Networks with Multiple Sources and Sinks, with Applications to Oil and Gas Lease Investment Programs
The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for Optimality
Polymatroidal flow network models with multiple sinks
M/G/c Queueing Systems with Multiple Customer Classes: Characterization and Control of Achievable Performance Under Nonpreemptive Priority Rules
Characterization and Optimization of Achievable Performance in General Queueing Systems
Efficient Algorithms for a Selection Problem with Nested Constraints and Its Application to a Production-Sales Planning Model
Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
Simple Ranking Methods for Allocation of One Resource
Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
Optimal sharing
Solution techniques for some allocation problems
Computing Maximal “Polymatroidal” Network Flows
Optimal flows in networks with multiple sources and sinks
The Sharing Problem
A 98%-Effective Lot-Sizing Rule for a Multi-Product, Multi-Stage Production / Inventory System
Activity selection games and the minimum‐cut problem