An algorithm is a formal procedure that describes how to solve a problem. For instance, the simplex algorithm in Chapter 2 takes as input a linear program in standard equality form and either returns an optimal solution, or detects that the linear program is infeasible or unbounded. Another example is the shortest path algorithm in Chapter 3.1. It takes as input a graph with distinct vertices s, t and nonnegative integer edge lengths, and returns an st-path of shortest length (if one exists).
The two basic properties we require for an algorithm are: correctness and termination. By correctness, we mean that the algorithm is always accurate when it claims that we have a particular outcome. One way to ensure this is to require that the algorithm provides a certificate, i.e. a proof, to justify its answers. By termination, we mean that the algorithm will stop after a finite number of steps.
In Section A.1, we will define the running time of an algorithm; we will formalize the notions of slow and fast algorithms. Section A.2 reviews the algorithms presented in this book and discusses which ones are fast and which ones are slow. In Sections A.3 and A.4 we discuss the inherent complexity of various classes of optimization problems and discuss the possible existence of classes of problems for which it is unlikely that any fast algorithm exists. We explain how an understanding of computational complexity can guide us in the design of algorithms.
Review the options below to login to check your access.
Log in with your Cambridge Aspire website account to check access.
If you believe you should have access to this content, please contact your institutional librarian or consult our FAQ page for further information about accessing our content.