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

Karen Aardal, Pierre Le Bodic

Research output: Contribution to journalArticleScientificpeer-review

5 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)549-552
Number of pages4
JournalOperations Research Letters
Volume42
Issue number8
DOIs
Publication statusPublished - 2014

Keywords

  • Approximation algorithms
  • Transportation problem with market choice
  • Capacitated facility location

Fingerprint Dive into the research topics of 'Approximation algorithms for the transportation problem with market choice and related models'. Together they form a unique fingerprint.

Cite this