DOS Seminar

Event Details
  • Date/Time:
    • Friday April 11, 2014 - Saturday April 12, 2014
      4:00 pm - 4:59 pm
  • Location: IC 115
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: DOS Seminar

Full Summary: No summary paragraph submitted.

TITLE: A local-search based approximation algorithm for the transportation problem with market choice

SPEAKER:  Karen Aardal


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.

Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
Undergraduate students, Faculty/Staff, Graduate students
No keywords were submitted.
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Apr 7, 2014 - 6:08am
  • Last Updated: Apr 13, 2017 - 5:22pm