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