{"288691":{"#nid":"288691","#data":{"type":"event","title":"DOS Seminar","body":[{"value":"\u003Cp\u003ETITLE: A local-search based approximation algorithm for the transportation problem with market choice\u003C\/p\u003E\u003Cp\u003ESPEAKER:\u0026nbsp; Karen Aardal\u003C\/p\u003E\u003Cp\u003EABSTRACT:\u003C\/p\u003E\u003Cp class=\u0022gmail_default\u0022\u003EIn 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.\u003C\/p\u003E\u003Cp class=\u0022gmail_default\u0022\u003EThe transportation problem with market choice was introduced by Damci-Kurt, Dey, and K\u00fc\u00e7\u00fckyavuz, who show that TPMC is NP-hard, and examine the polyhedral structure. Here we derive a constant factor approximation algorithm based on local search.\u0026nbsp;\u003C\/p\u003E\u003Cp class=\u0022gmail_default\u0022\u003EThis is joint work with Pieter van den Berg and Shanfei Li.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"DOS Seminar"}],"uid":"27187","created_gmt":"2014-04-07 10:08:57","changed_gmt":"2017-04-13 21:22:45","author":"Anita Race","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-04-11T17:00:00-04:00","event_time_end":"2014-04-11T18:00:00-04:00","event_time_end_last":"2014-04-11T18:00:00-04:00","gmt_time_start":"2014-04-11 21:00:00","gmt_time_end":"2014-04-11 22:00:00","gmt_time_end_last":"2014-04-11 22:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"1242","name":"School of Industrial and Systems Engineering (ISYE)"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}