Assignment -

Consider the following problem: we are given a collection of customers {1, . . . , n} and a set of depots {1, ... , k}, as well as a non-negative distance matrix D such that did is the distance between customer i and depot j. We are looking for the shortest tour that visits each customer exactly once, but with the additional requirement that between visiting two customers, we must also visit one of the depots (we are allowed to use the same depot more than once). In other words, the tour alternates between customers and depots. Show that this problem can be solved in polynomial time if k is fixed.