{"product_id":"optimization-of-computer-networks-9781119013358","title":"Optimization of Computer Networks","description":"\u003cb\u003eBook Synopsis\u003c\/b\u003e\u003cbr\u003e\u003cp\u003eThis book covers the design and optimization of computer networks applying a rigorous optimization methodology, applicable to any network technology. It is organized into two parts. In Part 1 the reader will learn how to model network problems appearing in computer networks as optimization programs, and use optimization theory to give insights on them. Four problem types are addressed systematically  traffic routing, capacity dimensioning, congestion control and topology design.\u003c\/p\u003e \u003cp\u003ePart 2 targets the design of algorithms that solve network problems like the ones modeled in Part 1. Two main approaches are addressed  gradient-like algorithms inspiring distributed network protocols that dynamically adapt to the network, or cross-layer schemes that coordinate the cooperation among protocols; and those focusing on the design of heuristic algorithms for long term static network design and planning problems.\u003c\/p\u003e \u003cp\u003eFollowing a hands-on approach, the reader will have access to a large s\u003cbr\u003e\u003cbr\u003e\u003cb\u003eTrade Review\u003c\/b\u003e\u003cbr\u003e�This is an exceptional textbook smoothly linking optimization theory with practical issues of computer network design�Almost all chapters contain a special section entitled �Notes and Sources� reviewing the key literature, a set of exercises for students, and a comprehensive list of references. The book is full of useful design hints, lists of potential problems facing designers, as well as illustrative examples. Unlike many textbooks on optimization, this work smartly combines the depth of mathematical analysis with a very good understanding of practical engineering issues. One of the important added values of this book is that the code of the devised algorithms implemented in the Net2Plan tool is accessible and algorithm convergence of the case studies is illustrated in empirical tests. To sum it up, this is an excellent textbook not only for engineering students but also for researchers and practicing engineers working in the area of computer and telecommunication network design.� -\tAndrzej Jajszczyk, AGH University of Science and Technology in Krakow, Poland\u003cbr\u003e\u003cbr\u003e\u003cb\u003eTable of Contents\u003c\/b\u003e\u003cbr\u003e\u003c\/p\u003e\u003cp\u003eAbout the Author xv\u003c\/p\u003e \u003cp\u003ePreface xvii\u003c\/p\u003e \u003cp\u003eAcknowledgments xxi\u003c\/p\u003e \u003cp\u003e\u003cb\u003e1 Introduction 1\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e1.1 What is a Communication Network? 1\u003c\/p\u003e \u003cp\u003e1.2 Capturing the Random User Behavior 4\u003c\/p\u003e \u003cp\u003e1.3 Queueing Theory and Optimization Theory 5\u003c\/p\u003e \u003cp\u003e1.4 The Rationale and Organization of this Book 6\u003c\/p\u003e \u003cp\u003e1.4.1 Part I: Modeling 6\u003c\/p\u003e \u003cp\u003e1.4.2 Part II: Algorithms 7\u003c\/p\u003e \u003cp\u003e1.4.3 Basic Optimization Requisites: Appendices I, II, and III 10\u003c\/p\u003e \u003cp\u003e1.4.4 Net2Plan Tool: Appendix IV 11\u003c\/p\u003e \u003cp\u003e\u003cb\u003ePart I MODELING\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e\u003cb\u003e2 Definitions and Notation 15\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e2.1 Notation for Sets, Vectors and Matrices 15\u003c\/p\u003e \u003cp\u003e2.1.1 Norm Basics 15\u003c\/p\u003e \u003cp\u003e2.1.2 Set Basics 16\u003c\/p\u003e \u003cp\u003e2.2 Network Topology 17\u003c\/p\u003e \u003cp\u003e2.3 Installed Capacities 19\u003c\/p\u003e \u003cp\u003e2.4 Traffic Demands 19\u003c\/p\u003e \u003cp\u003e2.4.1 Unicast, Anycast, and Multicast Demands 20\u003c\/p\u003e \u003cp\u003e2.4.2 Elastic versus Inelastic Demands 21\u003c\/p\u003e \u003cp\u003e2.5 Traffic Routing 21\u003c\/p\u003e \u003cp\u003eReferences 22\u003c\/p\u003e \u003cp\u003e\u003cb\u003e3 Performance Metrics in Networks 23\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e3.1 Introduction 23\u003c\/p\u003e \u003cp\u003e3.2 Delay 23\u003c\/p\u003e \u003cp\u003e3.2.1 Link Delay 23\u003c\/p\u003e \u003cp\u003e3.2.2 End-to-End Delay 27\u003c\/p\u003e \u003cp\u003e3.2.3 Average Network Delay 27\u003c\/p\u003e \u003cp\u003e3.2.4 Convexity Properties 27\u003c\/p\u003e \u003cp\u003e3.3 Blocking Probability 28\u003c\/p\u003e \u003cp\u003e3.3.1 Link Blocking Probability 28\u003c\/p\u003e \u003cp\u003e3.3.2 Demand and Network Blocking Probability 30\u003c\/p\u003e \u003cp\u003e3.3.3 Other Blocking Estimations 31\u003c\/p\u003e \u003cp\u003e3.3.4 Convexity Properties 34\u003c\/p\u003e \u003cp\u003e3.4 Average Number of Hops 34\u003c\/p\u003e \u003cp\u003e3.5 Network Congestion 36\u003c\/p\u003e \u003cp\u003e3.6 Network Cost 36\u003c\/p\u003e \u003cp\u003e3.7 Network Resilience Metrics 37\u003c\/p\u003e \u003cp\u003e3.7.1 Shared Risk Groups 40\u003c\/p\u003e \u003cp\u003e3.7.2 Simplified Availability Calculations 41\u003c\/p\u003e \u003cp\u003e3.7.3 General Model 41\u003c\/p\u003e \u003cp\u003e3.8 Network Utility and Fairness in Resource Allocation 44\u003c\/p\u003e \u003cp\u003e3.8.1 Fairness in Resource Allocation 44\u003c\/p\u003e \u003cp\u003e3.8.2 Fairness and Utility Functions 45\u003c\/p\u003e \u003cp\u003e3.8.3 Convexity Properties 47\u003c\/p\u003e \u003cp\u003e3.9 Notes and Sources 47\u003c\/p\u003e \u003cp\u003e3.10 Exercises 49\u003c\/p\u003e \u003cp\u003eReferences 51\u003c\/p\u003e \u003cp\u003e\u003cb\u003e4 Routing Problems 53\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e4.1 Introduction 53\u003c\/p\u003e \u003cp\u003e4.2 Flow-Path Formulation 54\u003c\/p\u003e \u003cp\u003e4.2.1 Optimality Analysis 55\u003c\/p\u003e \u003cp\u003e4.2.2 Candidate Path List Pre-Computation 58\u003c\/p\u003e \u003cp\u003e4.2.3 Ranking of Paths Elaboration 58\u003c\/p\u003e \u003cp\u003e4.2.4 Candidate Path List Augmentation (CPLA) 59\u003c\/p\u003e \u003cp\u003e4.3 Flow-Link Formulation 61\u003c\/p\u003e \u003cp\u003e4.3.1 Flow Conservation Constraints 62\u003c\/p\u003e \u003cp\u003e4.3.2 Obtaining the Routing from xde Variables 63\u003c\/p\u003e \u003cp\u003e4.3.3 Optimality Analysis 64\u003c\/p\u003e \u003cp\u003e4.4 Destination-Link Formulation 65\u003c\/p\u003e \u003cp\u003e4.4.1 Obtaining the Routing Tables from xte Variables 67\u003c\/p\u003e \u003cp\u003e4.4.2 Some Properties of the Routing Table Representation 67\u003c\/p\u003e \u003cp\u003e4.4.3 Comparing Flow-Based and Destination-Based Routing 71\u003c\/p\u003e \u003cp\u003e4.5 Convexity Properties of Performance Metrics 71\u003c\/p\u003e \u003cp\u003e4.6 Problem Variants 72\u003c\/p\u003e \u003cp\u003e4.6.1 Anycast Routing 72\u003c\/p\u003e \u003cp\u003e4.6.2 Multicast Routing 74\u003c\/p\u003e \u003cp\u003e4.6.3 Non-Bifurcated Routing 75\u003c\/p\u003e \u003cp\u003e4.6.4 Integral Routing 77\u003c\/p\u003e \u003cp\u003e4.6.5 Destination-Based Shortest Path Routing 77\u003c\/p\u003e \u003cp\u003e4.6.6 SRG-Disjoint 1+1 Dedicated Protection Routing 79\u003c\/p\u003e \u003cp\u003e4.6.7 Shared Restoration Routing 80\u003c\/p\u003e \u003cp\u003e4.6.8 Multi-Hour Routing 81\u003c\/p\u003e \u003cp\u003e4.7 Notes and Sources 83\u003c\/p\u003e \u003cp\u003e4.8 Exercises 83\u003c\/p\u003e \u003cp\u003eReferences 86\u003c\/p\u003e \u003cp\u003e\u003cb\u003e5 Capacity Assignment Problems 88\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e5.1 Introduction 88\u003c\/p\u003e \u003cp\u003e5.2 Long-Term Capacity Planning Problem Variants 89\u003c\/p\u003e \u003cp\u003e5.2.1 Capacity Planning for Concave Costs 89\u003c\/p\u003e \u003cp\u003e5.2.2 Capacity Planning with Modular Capacities 94\u003c\/p\u003e \u003cp\u003e5.2.3 Multi-Period Capacity Planning 97\u003c\/p\u003e \u003cp\u003e5.3 Fast Capacity Allocation Problem Variants: Wireless Networks 98\u003c\/p\u003e \u003cp\u003e5.3.1 The Wireless Channel 99\u003c\/p\u003e \u003cp\u003e5.3.2 Wireless Networks 100\u003c\/p\u003e \u003cp\u003e5.3.3 Modeling Wireless Networks 101\u003c\/p\u003e \u003cp\u003e5.4 MAC Design in Hard-Interference Scenarios 104\u003c\/p\u003e \u003cp\u003e5.4.1 Optimization in Random Access Networks 105\u003c\/p\u003e \u003cp\u003e5.4.2 Optimization in Carrier-Sense Networks 109\u003c\/p\u003e \u003cp\u003e5.5 Transmission Power Optimization in Soft Interference Scenarios 113\u003c\/p\u003e \u003cp\u003e5.6 Notes and Sources 116\u003c\/p\u003e \u003cp\u003e5.7 Exercises 117\u003c\/p\u003e \u003cp\u003eReferences 118\u003c\/p\u003e \u003cp\u003e\u003cb\u003e6 Congestion Control Problems 120\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e6.1 Introduction 120\u003c\/p\u003e \u003cp\u003e6.2 NUM Model 121\u003c\/p\u003e \u003cp\u003e6.2.1 Utility Functions for Elastic and Inelastic Traffic 121\u003c\/p\u003e \u003cp\u003e6.2.2 Fair Congestion Control 122\u003c\/p\u003e \u003cp\u003e6.2.3 Optimality Conditions 123\u003c\/p\u003e \u003cp\u003e6.3 Case Study: TCP 124\u003c\/p\u003e \u003cp\u003e6.3.1 Window-Based Flow Control 125\u003c\/p\u003e \u003cp\u003e6.3.2 TCP Reno 126\u003c\/p\u003e \u003cp\u003e6.3.3 TCP Vegas 131\u003c\/p\u003e \u003cp\u003e6.4 Active Queue Management (AQM) 134\u003c\/p\u003e \u003cp\u003e6.4.1 A Simplified Model of the TCP-AQM Interplay 135\u003c\/p\u003e \u003cp\u003e6.5 Notes and Sources 136\u003c\/p\u003e \u003cp\u003e6.6 Exercises 137\u003c\/p\u003e \u003cp\u003eReferences 139\u003c\/p\u003e \u003cp\u003e\u003cb\u003e7 Topology Design Problems 141\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e7.1 Introduction 141\u003c\/p\u003e \u003cp\u003e7.2 Node Location Problems 142\u003c\/p\u003e \u003cp\u003e7.2.1 Problem Variants 143\u003c\/p\u003e \u003cp\u003e7.2.2 Results 144\u003c\/p\u003e \u003cp\u003e7.3 Full Topology Design Problems 146\u003c\/p\u003e \u003cp\u003e7.3.1 Problem Variants 148\u003c\/p\u003e \u003cp\u003e7.3.2 Results 150\u003c\/p\u003e \u003cp\u003e7.4 Multilayer Network Design 152\u003c\/p\u003e \u003cp\u003e7.5 Notes and Sources 154\u003c\/p\u003e \u003cp\u003e7.6 Exercises 154\u003c\/p\u003e \u003cp\u003eReferences 157\u003c\/p\u003e \u003cp\u003e\u003cb\u003ePart II ALGORITHMS\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e\u003cb\u003e8 Gradient Algorithms in Network Design 161\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e8.1 Introduction 161\u003c\/p\u003e \u003cp\u003e8.2 Convergence Rates 163\u003c\/p\u003e \u003cp\u003e8.3 Projected Gradient Methods 164\u003c\/p\u003e \u003cp\u003e8.3.1 Basic Gradient Projection Algorithm 165\u003c\/p\u003e \u003cp\u003e8.3.2 Scaled Projected Gradient Method 165\u003c\/p\u003e \u003cp\u003e8.3.3 Singular and Ill-Conditioned Problems 168\u003c\/p\u003e \u003cp\u003e8.4 Asynchronous and Distributed Algorithm Implementations 169\u003c\/p\u003e \u003cp\u003e8.5 Non-Smooth Functions 172\u003c\/p\u003e \u003cp\u003e8.6 Stochastic Gradient Methods 174\u003c\/p\u003e \u003cp\u003e8.7 Stopping Criteria 176\u003c\/p\u003e \u003cp\u003e8.8 Algorithm Design Hints 177\u003c\/p\u003e \u003cp\u003e8.8.1 Dimensioning the Step Size 177\u003c\/p\u003e \u003cp\u003e8.8.2 Discrete Step Length 178\u003c\/p\u003e \u003cp\u003e8.8.3 Heavy-Ball Methods 179\u003c\/p\u003e \u003cp\u003e8.9 Notes and Sources 181\u003c\/p\u003e \u003cp\u003e8.10 Exercises 181\u003c\/p\u003e \u003cp\u003eReferences 182\u003c\/p\u003e \u003cp\u003e\u003cb\u003e9 Primal Gradient Algorithms 184\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e9.1 Introduction 184\u003c\/p\u003e \u003cp\u003e9.2 Penalty Methods 185\u003c\/p\u003e \u003cp\u003e9.2.1 Interior Penalty Methods 185\u003c\/p\u003e \u003cp\u003e9.2.2 Exterior Penalty Methods 186\u003c\/p\u003e \u003cp\u003e9.3 Adaptive Bifurcated Routing 188\u003c\/p\u003e \u003cp\u003e9.3.1 Removing Equality Constraints 189\u003c\/p\u003e \u003cp\u003e9.3.2 Optimality and Stability 190\u003c\/p\u003e \u003cp\u003e9.3.3 Implementation Example 192\u003c\/p\u003e \u003cp\u003e9.4 Congestion Control using Barrier Functions 197\u003c\/p\u003e \u003cp\u003e9.4.1 Implementation Example 198\u003c\/p\u003e \u003cp\u003e9.4.2 Exterior Penalty 200\u003c\/p\u003e \u003cp\u003e9.5 Persistence Probability Adjustment in MAC Protocols 201\u003c\/p\u003e \u003cp\u003e9.5.1 Implementation Example 203\u003c\/p\u003e \u003cp\u003e9.6 Transmission Power Assignment in Wireless Networks 205\u003c\/p\u003e \u003cp\u003e9.6.1 Implementation Example 207\u003c\/p\u003e \u003cp\u003e9.7 Notes and Sources 210\u003c\/p\u003e \u003cp\u003e9.8 Exercises 211\u003c\/p\u003e \u003cp\u003eReferences 213\u003c\/p\u003e \u003cp\u003e\u003cb\u003e10 Dual Gradient Algorithms 214\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e10.1 Introduction 214\u003c\/p\u003e \u003cp\u003e10.2 Adaptive Routing in Data Networks 217\u003c\/p\u003e \u003cp\u003e10.2.1 Optimality and Stability 219\u003c\/p\u003e \u003cp\u003e10.2.2 Implementation Example 219\u003c\/p\u003e \u003cp\u003e10.3 Backpressure (Center-Free) Routing 221\u003c\/p\u003e \u003cp\u003e10.3.1 Relation between 𝛾, ΔP, and Average Queue Sizes, Qnd 224\u003c\/p\u003e \u003cp\u003e10.3.2 Implementation Example 225\u003c\/p\u003e \u003cp\u003e10.4 Congestion Control 228\u003c\/p\u003e \u003cp\u003e10.4.1 Optimality and Stability Conditions 229\u003c\/p\u003e \u003cp\u003e10.4.2 Implementation Example 230\u003c\/p\u003e \u003cp\u003e10.5 Decentralized Optimization of CSMA Window Sizes 231\u003c\/p\u003e \u003cp\u003e10.5.1 Implementation Example 234\u003c\/p\u003e \u003cp\u003e10.6 Notes and Sources 236\u003c\/p\u003e \u003cp\u003e10.7 Exercises 236\u003c\/p\u003e \u003cp\u003eReferences 238\u003c\/p\u003e \u003cp\u003e\u003cb\u003e11 Decomposition Techniques 240\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e11.1 Introduction 240\u003c\/p\u003e \u003cp\u003e11.2 Theoretical Fundamentals 241\u003c\/p\u003e \u003cp\u003e11.2.1 Primal Decomposition 241\u003c\/p\u003e \u003cp\u003e11.2.2 Dual Decomposition 244\u003c\/p\u003e \u003cp\u003e11.2.3 Other Decompositions 246\u003c\/p\u003e \u003cp\u003e11.3 Cross-Layer Congestion Control and QoS Capacity Allocation 247\u003c\/p\u003e \u003cp\u003e11.3.1 Implementation Example 249\u003c\/p\u003e \u003cp\u003e11.4 Cross-Layer Congestion Control and Backpressure Routing 249\u003c\/p\u003e \u003cp\u003e11.4.1 Implementation Example 252\u003c\/p\u003e \u003cp\u003e11.5 Cross-Layer Congestion Control and Power Allocation 253\u003c\/p\u003e \u003cp\u003e11.5.1 Implementation Example 254\u003c\/p\u003e \u003cp\u003e11.6 Multidomain Routing 256\u003c\/p\u003e \u003cp\u003e11.6.1 Implementation Example 258\u003c\/p\u003e \u003cp\u003e11.7 Dual Decomposition in Non-Convex Problems 259\u003c\/p\u003e \u003cp\u003e11.7.1 Implementation Example 261\u003c\/p\u003e \u003cp\u003e11.8 Notes and Sources 261\u003c\/p\u003e \u003cp\u003e11.9 Exercises 263\u003c\/p\u003e \u003cp\u003eReferences 265\u003c\/p\u003e \u003cp\u003e\u003cb\u003e12 Heuristic Algorithms 266\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e12.1 Introduction 266\u003c\/p\u003e \u003cp\u003e12.1.1 What Complexity Theory Tells us that We cannot Do 266\u003c\/p\u003e \u003cp\u003e12.1.2 Our Options 267\u003c\/p\u003e \u003cp\u003e12.1.3 Organization and Rationale of this Chapter 268\u003c\/p\u003e \u003cp\u003e12.2 Heuristic Design Keys 270\u003c\/p\u003e \u003cp\u003e12.2.1 Heuristic Types 270\u003c\/p\u003e \u003cp\u003e12.2.2 Intensification versus Diversification 271\u003c\/p\u003e \u003cp\u003e12.2.3 How to Assess the Solution Quality 271\u003c\/p\u003e \u003cp\u003e12.2.4 Stop Conditions 272\u003c\/p\u003e \u003cp\u003e12.2.5 Defining the Cost or Fitness Function 272\u003c\/p\u003e \u003cp\u003e12.2.6 Coding the Solution 273\u003c\/p\u003e \u003cp\u003e12.3 Local Search Algorithms 273\u003c\/p\u003e \u003cp\u003e12.3.1 Design Hints 274\u003c\/p\u003e \u003cp\u003e12.4 Simulated Annealing 276\u003c\/p\u003e \u003cp\u003e12.4.1 Design hints 277\u003c\/p\u003e \u003cp\u003e12.5 Tabu Search 278\u003c\/p\u003e \u003cp\u003e12.5.1 Design Hints 280\u003c\/p\u003e \u003cp\u003e12.6 Greedy Algorithms 281\u003c\/p\u003e \u003cp\u003e12.7 GRASP 282\u003c\/p\u003e \u003cp\u003e12.8 Ant Colony Optimization 283\u003c\/p\u003e \u003cp\u003e12.8.1 Design Hints 286\u003c\/p\u003e \u003cp\u003e12.9 Evolutionary Algorithms 288\u003c\/p\u003e \u003cp\u003e12.9.1 Design Hints 289\u003c\/p\u003e \u003cp\u003e12.10 Case Study: Greenfield Plan with Recovery Schemes Comparison 291\u003c\/p\u003e \u003cp\u003e12.10.1 Case Study Description 291\u003c\/p\u003e \u003cp\u003e12.10.2 Algorithm Description 293\u003c\/p\u003e \u003cp\u003e12.10.3 Combining Heuristics and ILPs 295\u003c\/p\u003e \u003cp\u003e12.10.4 Results 296\u003c\/p\u003e \u003cp\u003e12.11 Notes and Sources 297\u003c\/p\u003e \u003cp\u003e12.12 Exercises 297\u003c\/p\u003e \u003cp\u003eReferences 299\u003c\/p\u003e \u003cp\u003e\u003cb\u003eA Convex Sets. Convex Functions 301\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003eA.1 Convex Sets 301\u003c\/p\u003e \u003cp\u003eA.2 Convex and Concave Functions 303\u003c\/p\u003e \u003cp\u003eA.2.1 Convexity in Differentiable Functions 303\u003c\/p\u003e \u003cp\u003eA.2.2 Strong Convexity\/Concavity 306\u003c\/p\u003e \u003cp\u003eA.2.3 Convexity in Non-Differentiable Functions 306\u003c\/p\u003e \u003cp\u003eA.2.4 Determining the Curvature of a Function 307\u003c\/p\u003e \u003cp\u003eA.2.5 Sub-level Sets 310\u003c\/p\u003e \u003cp\u003eA.2.6 Epigraphs 311\u003c\/p\u003e \u003cp\u003eA.3 Notes and Sources 311\u003c\/p\u003e \u003cp\u003eReference 312\u003c\/p\u003e \u003cp\u003e\u003cb\u003eB Mathematical Optimization Basics 313\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003eB.1 Optimization Problems 313\u003c\/p\u003e \u003cp\u003eB.2 A Classification of Optimization Problems 315\u003c\/p\u003e \u003cp\u003eB.2.1 Linear Programming 315\u003c\/p\u003e \u003cp\u003eB.2.2 Convex Programs 318\u003c\/p\u003e \u003cp\u003eB.2.3 Nonlinear Programs 320\u003c\/p\u003e \u003cp\u003eB.2.4 Integer Programs 321\u003c\/p\u003e \u003cp\u003eB.3 Duality 324\u003c\/p\u003e \u003cp\u003eB.3.1 Dual Function 324\u003c\/p\u003e \u003cp\u003eB.4 Optimality Conditions 330\u003c\/p\u003e \u003cp\u003eB.4.1 Optimality Conditions in Problems with Strong Duality 330\u003c\/p\u003e \u003cp\u003eB.4.2 Graphical Interpretation of KKT Conditions 333\u003c\/p\u003e \u003cp\u003eB.4.3 Optimality Conditions in Problems Without Strong Duality 336\u003c\/p\u003e \u003cp\u003eB.5 Sensitivity Analysis 337\u003c\/p\u003e \u003cp\u003eB.6 Notes and Sources 339\u003c\/p\u003e \u003cp\u003eReferences 340\u003c\/p\u003e \u003cp\u003e\u003cb\u003eC Complexity Theory 341\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003eC.1 Introduction 341\u003c\/p\u003e \u003cp\u003eC.2 Deterministic Machines and Deterministic Algorithms 342\u003c\/p\u003e \u003cp\u003eC.2.1 Complexity of a Deterministic Algorithm 342\u003c\/p\u003e \u003cp\u003eC.2.2 Worst-Case Algorithm Complexity 343\u003c\/p\u003e \u003cp\u003eC.2.3 Asymptotic Algorithm Complexity 343\u003c\/p\u003e \u003cp\u003eC.2.4 Complexity is a Real Barrier 345\u003c\/p\u003e \u003cp\u003eC.3 Non-Deterministic Machines and Non-Deterministic Algorithms 346\u003c\/p\u003e \u003cp\u003eC.3.1 Complexity of a Non-Deterministic Algorithm 347\u003c\/p\u003e \u003cp\u003eC.4 \u003ci\u003eN\u003c\/i\u003e and \u003ci\u003eNP\u003c\/i\u003e Complexity Classes 347\u003c\/p\u003e \u003cp\u003eC.5 Polynomial Reductions 349\u003c\/p\u003e \u003cp\u003eC.5.1 A Polynomial Time Reduction Example 350\u003c\/p\u003e \u003cp\u003eC.6 \u003ci\u003eNP\u003c\/i\u003e-Completeness 351\u003c\/p\u003e \u003cp\u003eC.6.1 An Example Proving \u003ci\u003eNP\u003c\/i\u003e-Completeness for a Problem 352\u003c\/p\u003e \u003cp\u003eC.7 Optimization Problems and Approximation Schemes 352\u003c\/p\u003e \u003cp\u003eC.7.1 The \u003ci\u003eNPʘ\u003c\/i\u003e Class 353\u003c\/p\u003e \u003cp\u003eC.7.2 Approximation Algorithms 354\u003c\/p\u003e \u003cp\u003eC.7.3 \u003ci\u003ePTAS\u003c\/i\u003e Reductions 356\u003c\/p\u003e \u003cp\u003eC.7.4 \u003ci\u003eNPʘ\u003c\/i\u003e-Complete Problems 356\u003c\/p\u003e \u003cp\u003eC.8 Complexity of Network Design Problems 357\u003c\/p\u003e \u003cp\u003eC.9 Notes and Sources 357\u003c\/p\u003e \u003cp\u003eReferences 358\u003c\/p\u003e \u003cp\u003e\u003cb\u003eD Net2Plan 359\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003eD.1 Net2Plan 359\u003c\/p\u003e \u003cp\u003eD.2 On the Role of Net2Plan in this Book 360\u003c\/p\u003e \u003cp\u003eIndex 363\u003c\/p\u003e","brand":"John Wiley \u0026 Sons Inc","offers":[{"title":"Default Title","offer_id":49406966792535,"sku":"9781119013358","price":66.45,"currency_code":"GBP","in_stock":true}],"thumbnail_url":"\/\/cdn.shopify.com\/s\/files\/1\/0817\/1739\/5799\/files\/9781119013358.jpg?v=1730497723","url":"https:\/\/bookcurl.com\/products\/optimization-of-computer-networks-9781119013358","provider":"Book Curl","version":"1.0","type":"link"}