| Preface |
|
xi | |
| Acknowledgments |
|
xvii | |
|
|
|
1 | (40) |
|
|
|
1 | (2) |
|
1.2 Equitable Resource Allocation: Lexicographic Minimax (Maximin) Optimization |
|
|
3 | (11) |
|
1.3 Examples and Applications |
|
|
14 | (12) |
|
1.3.1 Allocation of High-Tech Components |
|
|
14 | (1) |
|
1.3.2 Throughput in Communication and Computer Networks |
|
|
15 | (3) |
|
1.3.3 Point-to-Point Throughput Estimation in Networks |
|
|
18 | (2) |
|
1.3.4 Bandwidth Allocation for Content Distribution |
|
|
20 | (3) |
|
1.3.5 Location of Emergency Facilities |
|
|
23 | (2) |
|
|
|
25 | (1) |
|
1.4 Related Fairness Criteria |
|
|
26 | (4) |
|
|
|
30 | (5) |
|
1.5.1 Chapter 2: Nonlinear Resource Allocation |
|
|
30 | (1) |
|
1.5.2 Chapter 3: Equitable Resource Allocation: Lexicographic Minimax and Maximin Optimization |
|
|
30 | (1) |
|
1.5.3 Chapter 4: Equitable Resource Allocation with Substitutable Resources |
|
|
31 | (1) |
|
1.5.4 Chapter 5: Multiperiod Equitable Resource Allocation |
|
|
32 | (1) |
|
1.5.5 Chapter 6: Equitable Network Resource Allocation |
|
|
33 | (1) |
|
1.5.6 Chapter 7: Equitable Resource Allocation with Integer Decisions |
|
|
34 | (1) |
|
1.6 Concluding Remarks and Literature Review |
|
|
35 | (6) |
|
1.6.1 Equitable Allocation of High-Tech Components |
|
|
38 | (1) |
|
1.6.2 Equitable Throughput in Communication and Computer Networks |
|
|
38 | (1) |
|
1.6.3 Point-to-Point Throughput Estimation in Networks |
|
|
39 | (1) |
|
1.6.4 Equitable Bandwidth Allocation for Content Distribution |
|
|
39 | (1) |
|
1.6.5 Equitable Location of Emergency Facilities |
|
|
39 | (1) |
|
|
|
39 | (2) |
|
2 Nonlinear Resource Allocation |
|
|
41 | (36) |
|
2.1 Formulation and Optimality Properties |
|
|
42 | (6) |
|
|
|
48 | (10) |
|
2.2.1 The Activity Deletion Algorithm |
|
|
48 | (5) |
|
2.2.2 The Activity Addition Algorithm |
|
|
53 | (2) |
|
2.2.3 The Constraints Evaluation Algorithm |
|
|
55 | (3) |
|
2.2.4 Lower and Upper Bounds |
|
|
58 | (1) |
|
2.3 Nonlinear Resource-Usage Constraint |
|
|
58 | (8) |
|
2.3.1 Formulation and Optimality Properties |
|
|
59 | (3) |
|
|
|
62 | (4) |
|
2.4 Multiple Resource Constraints: A Special Case |
|
|
66 | (7) |
|
2.5 Concluding Remarks and Literature Review |
|
|
73 | (4) |
|
|
|
75 | (2) |
|
3 Equitable Resource Allocation: Lexicographic Minimax and Maximin Optimization |
|
|
77 | (46) |
|
3.1 Formulation and Optimality Properties |
|
|
78 | (6) |
|
|
|
84 | (14) |
|
3.2.1 The Minimax Activity Deletion Algorithm |
|
|
84 | (6) |
|
3.2.2 The Minimax Activity Addition Algorithm |
|
|
90 | (4) |
|
3.2.3 The Minimax Constraints Evaluation Algorithm |
|
|
94 | (3) |
|
3.2.4 Lower and Upper Bounds |
|
|
97 | (1) |
|
3.3 The Lexicographic Minimax Algorithm |
|
|
98 | (9) |
|
3.4 Extension to Nonseparable Objective Function |
|
|
107 | (9) |
|
3.5 Concluding Remarks and Literature Review |
|
|
116 | (7) |
|
|
|
120 | (3) |
|
4 Equitable Resource Allocation with Substitutable Resources |
|
|
123 | (60) |
|
4.1 Representations of Substitutable Resources |
|
|
124 | (7) |
|
4.1.1 Transitive Substitutable Resources Represented by Trees |
|
|
124 | (1) |
|
4.1.2 Transitive Substitutable Resources Represented by Acyclic Graphs |
|
|
125 | (2) |
|
4.1.3 Nontransitive Substitutable Resources Represented by Bipartite Graphs |
|
|
127 | (1) |
|
4.1.4 Activity-Dependent Substitutable Resources Represented by Bipartite Graphs |
|
|
128 | (1) |
|
|
|
129 | (2) |
|
4.2 Transitive Substitutable Resources Represented by Trees |
|
|
131 | (22) |
|
|
|
131 | (3) |
|
4.2.2 The Minimax Algorithm |
|
|
134 | (9) |
|
4.2.3 The Lexicographic Minimax Algorithm |
|
|
143 | (8) |
|
4.2.4 Lower and Upper Bounds |
|
|
151 | (2) |
|
4.3 Transitive Substitutable Resources Represented by Acyclic Graphs |
|
|
153 | (19) |
|
|
|
154 | (1) |
|
4.3.2 The Feasibility Problem |
|
|
155 | (6) |
|
4.3.3 The Minimax Algorithm |
|
|
161 | (4) |
|
4.3.4 The Lexicographic Minimax Algorithm |
|
|
165 | (7) |
|
4.4 Activity-Dependent Substitutable Resources Represented by Bipartite Graphs |
|
|
172 | (8) |
|
|
|
173 | (2) |
|
4.4.2 The Minimax Algorithm |
|
|
175 | (4) |
|
4.4.3 The Lexicographic Minimax Algorithm |
|
|
179 | (1) |
|
4.5 Concluding Remarks and Literature Review |
|
|
180 | (3) |
|
|
|
181 | (2) |
|
5 Multiperiod Equitable Resource Allocation |
|
|
183 | (38) |
|
5.1 Formulation for Storable Resource Allocation |
|
|
184 | (3) |
|
5.2 Minimax Algorithms for Storable Resources |
|
|
187 | (16) |
|
5.2.1 The Search-Based Algorithm |
|
|
188 | (4) |
|
5.2.2 The Transformation-Based Algorithm |
|
|
192 | (8) |
|
5.2.3 The Multiperiod Activity Deletion Algorithm: A Special Case |
|
|
200 | (3) |
|
5.3 The Lexicographic Minimax Algorithm |
|
|
203 | (7) |
|
5.4 Allocation of Nonstorable Resources |
|
|
210 | (3) |
|
5.5 Multiperiod Allocation of Substitutable Resources |
|
|
213 | (5) |
|
5.6 Concluding Remarks and Literature Review |
|
|
218 | (3) |
|
|
|
219 | (2) |
|
6 Equitable Allocation of Network Resources |
|
|
221 | (38) |
|
6.1 Multicommodity Network Flows with a Single Fixed Path |
|
|
223 | (4) |
|
6.2 Multicommodity Network Flows with Multiple Paths |
|
|
227 | (10) |
|
6.3 Bandwidth Allocation for Content Distribution |
|
|
237 | (11) |
|
6.4 Content Distribution with Node-Dependent Performance Functions |
|
|
248 | (6) |
|
6.5 Concluding Remarks and Literature Review |
|
|
254 | (5) |
|
|
|
257 | (2) |
|
7 Equitable Resource Allocation with Integer Decisions |
|
|
259 | (54) |
|
7.1 Knapsack Resource Constraints with Integer Variables |
|
|
261 | (12) |
|
7.1.1 Formulation and Challenges |
|
|
261 | (3) |
|
7.1.2 The Integer Minimax Problem |
|
|
264 | (6) |
|
7.1.3 The Integer Lexicographic Minimax Problem with One Resource Constraint |
|
|
270 | (3) |
|
7.2 Problems with a Limited Number of Distinct Outcomes |
|
|
273 | (17) |
|
7.2.1 The Equitable Facility Location Problem |
|
|
273 | (6) |
|
7.2.2 The Equitable Sensor Location Problem |
|
|
279 | (2) |
|
7.2.3 Lexicographic Minimization of Counting Functions |
|
|
281 | (9) |
|
7.3 Problems with a Large Number of Distinct Outcomes |
|
|
290 | (17) |
|
|
|
291 | (3) |
|
7.3.2 Lexicographic Maximization of Performance Function Values |
|
|
294 | (7) |
|
7.3.3 The Conditional Maximin Approach |
|
|
301 | (1) |
|
7.3.4 The Ordered Weighted Averaging Approach |
|
|
302 | (3) |
|
7.3.5 The Convex Integer Optimization Approach |
|
|
305 | (2) |
|
7.4 Concluding Remarks and Literature Review |
|
|
307 | (6) |
|
|
|
311 | (2) |
|
|
|
313 | (18) |
|
Appendix A Summary of Models and Algorithms |
|
|
315 | (8) |
|
Appendix B The Kuhn-Tucker Conditions |
|
|
323 | (4) |
|
Appendix C Duality in Linear Programming |
|
|
327 | (4) |
| References |
|
331 | (12) |
| Author Index |
|
343 | (4) |
| Subject Index |
|
347 | |