Approximation Algorithms for the Traveling Purchaser Problem and.pdf.pdf' (225.54 kB)

Approximation Algorithms for the Traveling Purchaser Problem and Its Variants in Network Design

Download (225.54 kB)
journal contribution
posted on 01.07.1986 by Ramamoorthi Ravi, F. S. Salman
The traveling purchaser problem is a generalization of the traveling salesman problem with applications in a wide range of areas including network design and scheduling. The input consists of a set of markets and a set of products. Each market offers a price for each product and there is a cost associated with traveling from one market to another. The problem is to purchase all products by visiting a subset of the markets in a tour such that the total travel and purchase costs are minimized. This problem includes many well-known NP-hard problems such as uncapacitated facility location, set cover and group Steiner tree problems as its special cases. We give an approximation algorithm with a poly-logarithmic worst-case ratio for the traveling purchaser problem with metric travel costs. For a special case of the problem that models the ring-star network design problem, we give a constant factor approximation algorithm. Our algorithms are based on rounding LP relaxation solutions.