Approximation algorithms for the transportation problem with market choice and related models
Karen Aardal (TU Delft - Discrete Mathematics and Optimization, Centrum Wiskunde & Informatica (CWI))
Pierre Le Bodic (Georgia Institute of Technology)
More Info
expand_more
Abstract
Given facilities with capacities and clients with penalties and demands, the transportation problem with market choice consists in finding the minimum-cost way to partition the clients into unserved clients, paying the penalties, and into served clients, paying the transportation cost to serve them.
We give polynomial-time reductions from this problem and variants to the (un)capacitated facility location problem, directly yielding approximation algorithms, two with constant factors in the metric case, one with a logarithmic factor in the general case.