Equitable resource allocation : models, algorithms, and applications
著者
書誌事項
Equitable resource allocation : models, algorithms, and applications
(Wiley series on information and communications technologies)
John Wiley & Sons, c2012
大学図書館所蔵 全1件
  青森
  岩手
  宮城
  秋田
  山形
  福島
  茨城
  栃木
  群馬
  埼玉
  千葉
  東京
  神奈川
  新潟
  富山
  石川
  福井
  山梨
  長野
  岐阜
  静岡
  愛知
  三重
  滋賀
  京都
  大阪
  兵庫
  奈良
  和歌山
  鳥取
  島根
  岡山
  広島
  山口
  徳島
  香川
  愛媛
  高知
  福岡
  佐賀
  長崎
  熊本
  大分
  宮崎
  鹿児島
  沖縄
  韓国
  中国
  タイ
  イギリス
  ドイツ
  スイス
  フランス
  ベルギー
  オランダ
  スウェーデン
  ノルウェー
  アメリカ
注記
Includes bibliographical references (p. 331-341) and indexes
内容説明・目次
内容説明
A unique book that specifically addresses equitable resource allocation problems with applications in communication networks, manufacturing, emergency services, and more Resource allocation problems focus on assigning limited resources in an economically beneficial way among competing activities. Solutions to such problems affect people and everyday activities with significant impact on the private and public sectors and on society at large.
Using diverse application areas as examples, Equitable Resource Allocation: Models, Algorithms, and Applications provides readers with great insight into a topic that is not widely known in the field. Starting with an overview of the topics covered, the book presents a large variety of resource allocation models with special mathematical structures and provides elegant, efficient algorithms that compute optimal solutions to these models.
Authored by one of the leading researchers in the field, Equitable Resource Allocation:
Is the only book that provides a comprehensive exposition of equitable resource allocation problems
Presents a collection of resource allocation models with applications in communication networks, transportation, content distribution, manufacturing, emergency services, and more
Exhibits practical algorithms for solving a variety of resource allocation models
Uses real-world applications and examples to explain important concepts
Includes end-of-chapter exercises
Bringing together much of the equitable resource allocation research from the past thirty years, this book is a valuable reference for anyone interested in solving diverse optimization problems.
目次
Preface xi Acknowledgments xvii
1 Introduction 1
1.1 Perspective 1
1.2 Equitable Resource Allocation: Lexicographic Minimax (Maximin) Optimization 3
1.3 Examples and Applications 14
1.3.1 Allocation of High-Tech Components 14
1.3.2 Throughput in Communication and Computer Networks 15
1.3.3 Point-to-Point Throughput Estimation in Networks 18
1.3.4 Bandwidth Allocation for Content Distribution 20
1.3.5 Location of Emergency Facilities 23
1.3.6 Other Applications 25
1.4 Related Fairness Criteria 26
1.5 Outline of the Book 30
1.5.1 Chapter 2: Nonlinear Resource Allocation 30
1.5.2 Chapter 3: Equitable Resource Allocation: Lexicographic Minimax and Maximin Optimization 30
1.5.3 Chapter 4: Equitable Resource Allocation with Substitutable Resources 31
1.5.4 Chapter 5: Multiperiod Equitable Resource Allocation 32
1.5.5 Chapter 6: Equitable Network Resource Allocation 33
1.5.6 Chapter 7: Equitable Resource Allocation with Integer Decisions 34
1.6 Concluding Remarks and Literature Review 35
1.6.1 Equitable Allocation of High-Tech Components 38
1.6.2 Equitable Throughput in Communication and Computer Networks 38
1.6.3 Point-to-Point Throughput Estimation in Networks 39
1.6.4 Equitable Bandwidth Allocation for Content Distribution 39
1.6.5 Equitable Location of Emergency Facilities 39
1.6.6 Other Applications 39
2 Nonlinear Resource Allocation 41
2.1 Formulation and Optimality Properties 42
2.2 Algorithms 48
2.2.1 The Activity Deletion Algorithm 48
2.2.2 The Activity Addition Algorithm 53
2.2.3 The Constraints Evaluation Algorithm 55
2.2.4 Lower and Upper Bounds 58
2.3 Nonlinear Resource-Usage Constraint 58
2.3.1 Formulation and Optimality Properties 59
2.3.2 Algorithms 62
2.4 Multiple Resource Constraints: A Special Case 66
2.5 Concluding Remarks and Literature Review 73
Exercises 75
3 Equitable Resource Allocation: Lexicographic Minimax and Maximin Optimization 77
3.1 Formulation and Optimality Properties 78
3.2 Minimax Algorithms 84
3.2.1 The Minimax Activity Deletion Algorithm 84
3.2.2 The Minimax Activity Addition Algorithm 90
3.2.3 The Minimax Constraints Evaluation Algorithm 94
3.2.4 Lower and Upper Bounds 97
3.3 The Lexicographic Minimax Algorithm 98
3.4 Extension to Nonseparable Objective Function 107
3.5 Concluding Remarks and Literature Review 116
Exercises 120
4 Equitable Resource Allocation with Substitutable Resources 123
4.1 Representations of Substitutable Resources 124
4.1.1 Transitive Substitutable Resources Represented by Trees 124
4.1.2 Transitive Substitutable Resources Represented by Acyclic Graphs 125
4.1.3 Nontransitive Substitutable Resources Represented by Bipartite Graphs 127
4.1.4 Activity-Dependent Substitutable Resources Represented by Bipartite Graphs 128
4.1.5 Solution Approach 129
4.2 Transitive Substitutable Resources Represented by Trees 131
4.2.1 Formulation 131
4.2.2 The Minimax Algorithm 134
4.2.3 The Lexicographic Minimax Algorithm 143
4.2.4 Lower and Upper Bounds 151
4.3 Transitive Substitutable Resources Represented by Acyclic Graphs 153
4.3.1 Formulation 154
4.3.2 The Feasibility Problem 155
4.3.3 The Minimax Algorithm 161
4.3.4 The Lexicographic Minimax Algorithm 165
4.4 Activity-Dependent Substitutable Resources Represented by Bipartite Graphs 172
4.4.1 Formulation 173
4.4.2 The Minimax Algorithm 175
4.4.3 The Lexicographic Minimax Algorithm 179
4.5 Concluding Remarks and Literature Review 180
Exercises 181
5 Multiperiod Equitable Resource Allocation 183
5.1 Formulation for Storable Resource Allocation 184
5.2 Minimax Algorithms for Storable Resources 187
5.2.1 The Search-Based Algorithm 188
5.2.2 The Transformation-Based Algorithm 192
5.2.3 The Multiperiod Activity Deletion Algorithm: A Special Case 200
5.3 The Lexicographic Minimax Algorithm 203
5.4 Allocation of Nonstorable Resources 210
5.5 Multiperiod Allocation of Substitutable Resources 213
5.6 Concluding Remarks and Literature Review 218
Exercises 219
6 Equitable Allocation of Network Resources 221
6.1 Multicommodity Network Flows with a Single Fixed Path 223
6.2 Multicommodity Network Flows with Multiple Paths 227
6.3 Bandwidth Allocation for Content Distribution 237
6.4 Content Distribution with Node-Dependent Performance Functions 248
6.5 Concluding Remarks and Literature Review 254
Exercises 257
7 Equitable Resource Allocation with Integer Decisions 259
7.1 Knapsack Resource Constraints with Integer Variables 261
7.1.1 Formulation and Challenges 261
7.1.2 The Integer Minimax Problem 264
7.1.3 The Integer Lexicographic Minimax Problem with One Resource Constraint 270
7.2 Problems with a Limited Number of Distinct Outcomes 273
7.2.1 The Equitable Facility Location Problem 273
7.2.2 The Equitable Sensor Location Problem 279
7.2.3 Lexicographic Minimization of Counting Functions 281
7.3 Problems with a Large Number of Distinct Outcomes 290
7.3.1 Examples 291
7.3.2 Lexicographic Maximization of Performance Function Values 294
7.3.3 The Conditional Maximin Approach 301
7.3.4 The Ordered Weighted Averaging Approach 302
7.3.5 The Convex Integer Optimization Approach 305
7.4 Concluding Remarks and Literature Review 307
Exercises 311
Appendices 313
Appendix A. Summary of Models and Algorithms / 315
Appendix B. The Kuhn-Tucker Conditions / 323
Appendix C. Duality in Linear Programming / 327
References 331
Author Index 343
Subject Index 347
「Nielsen BookData」 より