Question

(note: you have only 2 attempts.) for each of the following scenarios, decide which of the four problem types weve discussed in class (kwans mail carrier, traveling salesperson, network connection, or stable matching) is most closely related to the scenario.
(a) a band is scheduling a concert tour, and they want to spend as little time driving as possible. ?
(b) a subway inspector wants to check all of the tunnels for blockages, and wants to do so without going through the same tunnel more than once.
?
(c) after a tornado damaged most of the roads in a county, the local government needs to decide which roads to prioritize repairing in order to allow travel between every town in the county. ?
(d) graduating medical students are being assigned to hospitals for residencies. ?

Explanation:

• (a) The Traveling Salesperson problem aims to find the shortest possible route that visits a set of locations and returns to the starting point. Here, the band wants to minimize driving time (similar to minimizing route length in the Traveling Salesperson problem) while scheduling a concert tour (visiting multiple locations).
• (b) Kwan's Mail Carrier problem (also known as the Route Inspection problem) involves finding a shortest closed path that traverses every edge (in this case, tunnel) of a graph at least once. The subway inspector wants to check all tunnels (traverse all edges) without going through the same tunnel more than once (if possible, which relates to the concept of Eulerian trails/circuits in Kwan's Mail Carrier problem).
• (c) The Network Connection problem (related to finding a minimum - spanning tree) is about connecting all nodes (towns) in a graph (county with roads as edges) with the minimum number of edges (roads to repair) to ensure connectivity. The local government wants to repair roads (edges) to allow travel between every town (connect all nodes).
• (d) The Stable Matching problem is about finding a stable way to pair two sets of elements. Here, graduating medical students (one set) are being assigned to hospitals (another set) for residencies, which is similar to the concept of stable matching (matching students to hospitals in a stable way).

Answer:

(a) Traveling Salesperson
(b) Kwan's Mail Carrier
(c) Network Connection
(d) Stable Matching