Optimization Online


Approximation algorithms for the Transportation Problem with Market Choice and related models

Karen Aardal(k.i.aardal***at***tudelft.nl)
Pierre Le Bodic(lebodic***at***gatech.edu)

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.

Keywords: approximation algorithms, transportation problem with market choice, capacitated facility location

Category 1: Combinatorial Optimization (Approximation Algorithms )


Download: [PDF]

Entry Submitted: 09/25/2014
Entry Accepted: 09/25/2014
Entry Last Modified: 09/25/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society