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.
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.
Original language | English |
---|---|
Pages (from-to) | 549-552 |
Number of pages | 4 |
Journal | Operations Research Letters |
Volume | 42 |
Issue number | 8 |
DOIs | |
Publication status | Published - 2014 |
Keywords
- Approximation algorithms
- Transportation problem with market choice
- Capacitated facility location