Resource Allocation Problems: Algorithmic Approaches
This book addresses a theoretical problem encountered in a variety of areas in operations research and management science, including load distribution, production planning, computer scheduling, portfolio selection, and apportionment. It is a timely and comprehensive summary of the past thirty years of research on algorithmic aspects of the resource allocation problem and its variants, covering Lagrangean multiplier method, dynamic programming, greedy algorithms, and their generalizations. Modern data structures are used to analyze the computational complexity of each algorithm.
The resource allocation problem the authors take up is an optimization problem with a single simple constraint: it determines the allocation of a fixed amount of resources to a given number of activities in order to achieve the most effective results. It may be viewed as a special case of the nonlinear programming or nonlinear integer programming problem.
Introduction. Resource Allocation with Continuous Variables. Resource Allocation with Integer Variables. Minimizing a Convex Separable Function. Minimax and Maximin Resource Allocation Problems. Fair Resource Allocation Problem. Apportionment Problem. Fundamentals of Submodular Systems. Resource Allocation Problems under Submodular Constraints. Further Topics on Resource Allocation Problems. Appendixes: Algorithms and Complexity. NP-completeness and NP-hardness.
Toshihide lbaraki is Professor in the Department of Applied Mathematics and Physics at Kyoto University and Naoki Katoh is Associate Professor in the Department of Management Science at Kobe University of Commerce. Resource Allocation Problems is included in the Foundations of Computing Series edited by Michael Garey and Albert Meyer.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Resource Allocation with Continuous Variables
Resource Allocation with Integer Variables
8 other sections not shown
Other editions - View all
applying assume binary search chapter computes an optimal continuous relaxation convex function correctly computes decision problem defined dep(x discussed divisor method dj(y DSCDR dynamic programming example fair resource allocation feasible solution fj(xj given halt holds Ibaraki implies INCREMENT Input integer vector joint points Kuhn-Tucker conditions Lagrange multiplier lemma linear programming max fj(xj maximal vector maximum flow MINIMAX minimize minimum minimum cut nondecreasing nonlinear programming nonnegative integer NP-complete NP-hard Nth smallest element NTWKDR objective function objective value obtained optimal value optimization problem Output partition PDR(A polymatroid polynomial time algorithms population monotone positive integer problem instance problem SCDR procedure SM proves real number requires 0(n resource allocation problem respectively return to step sat(x satisfying SELECT2 selection algorithm SMCDR SMINCREMENT solution of SCDR submodular constraint submodular function submodular system subsets TREEDR x e P(r