Approximation Algorithms for Facility Location Problems and Other Supply Chain Problems

This thesis gives approximation algorithms for a series of NP-hard supply chain problems, that range from the packing, the distribution, and the inventory management of items, to the design of the supply network. Several novel techniques are employed in these approximations, and many of them may be extended to di erent problems. In the Metric Facility Location Problem (FLP), given sets of clients and facilities in a metric space, the objective is to open a subset of facilities, such that the cost to open facilities, and the cost to connect each client to an open facility is minimum. This work considers the case when the distance function is the square of a metric, which is suitable for many applications that do not satisfy the metric assumption. A lower bound of 2.04 on the approximation factor is given, and it is shown that an LP-rounding algorithm matches this factor. More interestingly, a new technique to obtain factor-revealing programs is presented, and it is used to analyze primal-dual algorithms, giving tight factors under a squared metric, or improving known factors under a metric. Also, it is shown that the Continuous FLP (ConFL), when a facility location is any point of the Euclidean space, may be reduced to the FLP by using the so called center sets. Center sets for the L2 -norm are given, and thus approximations for ConFL with this norm are derived, for – Ø 1. As a by-product, a PTAS for k-medians with the L2 -norm is obtained. The Production and Distribution Problem (PDP) is the problem of minimizing ordering, transportation and inventory costs of a supply chain formed by a set of warehouses and retailers over a finite time horizon. This is a common generalization of the FLP, and the Joint Replenishment Problem (JRP), and allows the coordination of network design and inventory management decisions, thus leading to significant economy. A 2.77approximation for the PDP is given under the assumption that holding and distribution cost functions satisfy a natural extension of the triangle inequality. Other generalizations of the JRP are also considered, such as the One-Warehouse Multiple-Retailer Problem (OWMR), for which a 5-approximation is given in the case that warehouse and retailer inventory costs are independent. Under this assumption, no approximation algorithm was known previously. Finally, there are given APTAS’s for the circle bin packing, and the circle strip packing.