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.