Approximation algorithms for the transportation problem with market choice and related models

Journal article (2014)

Authors

K. Aardal Discrete Mathematics and Optimization - EEMCS , Centrum Wiskunde & Informatica (CWI)
Pierre Le Bodic Georgia Institute of Technology
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
More Info
expand_more

Published Date

2014

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

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.