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

DOI10.1016/0377-2217(91)90300-KzbMath0745.90059MaRDI QIDQ1179000

S. Singh

Publication date: 26 June 1992

Published in: European Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

rank functionpolymatroid

Mathematics Subject Classification ID

Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Efficient, fair, and strategy-proof (re)allocation under network constraints, Convexity and Steinitz's exchange property, Algorithms for separable convex optimization with linear ascending constraints, Optimization problems with color-induced budget constraints, Equilibrium computation in resource allocation games, Fast integer-valued algorithms for optimal allocations under constraints in stratified sampling, A short proof of optimality of the bottom up algorithm for discrete resource allocation problems, A New Combinatorial Algorithm for Separable Convex Resource Allocation with Nested Bound Constraints, On a Reduction for a Class of Resource Allocation Problems, Sensitivity Analysis for Convex Separable Optimization Over Integral Polymatroids, Equivalence of convex minimization problems over base polytopes, Submodular functions: from discrete to continuous domains, Minimization of an M-convex function, Priority classes and weighted constrained equal awards rules for the claims problem, Theory of Principal Partitions Revisited, A logarithmic approximation for polymatroid congestion games, Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem., Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints, A polynomial algorithm for resourse allocation problems with polymatroid constrains¹, Computation and efficiency of potential function minimizers of combinatorial congestion games, Coordinatewise domain scaling algorithm for M-convex function minimization, Optimization and mechanism design, Eisenberg-Gale markets: algorithms and game-theoretic properties, Minimum entropy orientations, Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times, Optimization Problems with Color-Induced Budget Constraints, Active-set Methods for Submodular Minimization Problems, Submodular optimization views on the random assignment problem, Decreasing minimization on M-convex sets: background and structures, Decreasing minimization on base-polyhedra: relation between discrete and continuous cases

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