The garage sale problem (courtesy of Professor Lofti Zadeh). On a given Sunday m

Question

The garage sale problem (courtesy of Professor Lofti Zadeh). On a given Sunday morning, there are n garage sales going on, g1,g2,...,gn. For each garage sale gj, you have an estimate of its value to you, vj. For any two garage sales you have an estimate of the transportation cost dij of getting from gi to gj. You are also given the costs d0j and dj0 of going between your home and each garage sale. You want to find a tour of a subset of the given garage sales, starting and ending at home, that maximizes your total benefit minus your total transportation costs. Give an algorithm that solves this problem in time O(n22n). (Hint: This is closely related to the traveling salesman problem.)

Explanation / Answer

The Held-Karp algorithm should suffice to solve your question. It has O(n^2 2^n) complexity. Dynamic programming algorithm by Held and Karp and independently Bellman runs as follows: for each pair (S,ci), meaning a path going through c1, all the elements of S and terminating at ci compute OPT[S,ci]=min{OPT[S{ci},cj]+d(cj,ci):cj ? S{ci}}, where d(cj,ci) means the distance between cities cj and ci. It uses a "Branch and bound" approach to solve the TSP (that is where the 2^n factor of complexity comes from). There are n * 2^n sub-problems. Each of which takes linear i.e O(n) time to solve. Therefore total running time is O(n^2 2^n) Now for the Garage sale, we need to recalibrate the costs as follows: Firstly, there are 2 problems: 1. TSP of going to each garage 2. Dynamic programming where best solution = MAX(Garage sale value - TSP Cost) A straight-forward change in the Held-Karp algorithm should solve this: Just add Gj to each garage j visited and calculate the new objective function which maximizes the difference between Gj and Dij

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.