Skip to main content Accessibility help
Internet Explorer 11 is being discontinued by Microsoft in August 2021. If you have difficulties viewing the site on Internet Explorer 11 we recommend using a different browser such as Microsoft Edge, Google Chrome, Apple Safari or Mozilla Firefox.

Chapter 3: Duality through examples

Chapter 3: Duality through examples

pp. 99-141

Authors

, University of Waterloo, Ontario, , University of Waterloo, Ontario, , University of Waterloo, Ontario
Resources available Unlock the full potential of this textbook with additional resources. There are Instructor restricted resources available for this textbook. Explore resources
  • Add bookmark
  • Cite
  • Share

Summary

In this chapter, we revisit the shortest path and minimum-cost matching problems. Both were first introduced in Chapter 1, where we discussed practical example applications. We further showed that these problems can be expressed as IPs. The focus in this chapter will be on solving instances of the shortest path and matching problems. Our starting point will be to use the IP formulation we introduced in Section 1.5. We will show that studying the two problems through the lens of linear programming duality will allow us to design efficient algorithms. We develop this theory further in Chapter 4.

The shortest path problem

Recall the shortest path problem from Section 1.4.1. We are given a graph G = (V, E), nonnegative lengths ce for all edges eE, and two distinct vertices s, tV. The length c(P) of a path P is the sum of the length of its edges, i.e. Σ(ce: eP). We wish to find among all possible st-paths one that is of minimum length.

Example 7 In the following figure, we show an instance of this problem. Each of the edges in the graph is labeled by its length. The thick black edges in the graph form an st-path P = sa, ac, cb, bt of total length 3 + 1 + 2 + 1 = 7. This st-path is of minimum length, hence is a solution to our problem.

About the book

Access options

Review the options below to login to check your access.

Purchase options

eTextbook
US$58.00
Hardback
US$123.00
Paperback
US$58.00

Have an access code?

To redeem an access code, please log in with your personal login.

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.

Also available to purchase from these educational ebook suppliers