*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
TITLE: A local-search based approximation algorithm for the transportation problem with market choice
SPEAKER: Karen Aardal
ABSTRACT:
In the transportation problem with market choice we are given a set of markets with demands and a set of facilities with limited capacities in a common metric space. Each market is either accepted or rejected. For each accepted market, its demand has to be fully satisfied by facilities, which incurs transportation cost. For each rejected market, a penalty cost has to be paid. The goal is to decide which markets should be accepted and which should be rejected, such that the sum of transportation and penalty cost is minimized.
The transportation problem with market choice was introduced by Damci-Kurt, Dey, and Küçükyavuz, who show that TPMC is NP-hard, and examine the polyhedral structure. Here we derive a constant factor approximation algorithm based on local search.
This is joint work with Pieter van den Berg and Shanfei Li.
