Approximation algorithms for the transportation problem with market choice and related models

作     者：Aardal, Karen Le Bodic, Pierre 

作者机构：Delft Univ Technol Delft Inst Appl Math Delft Netherlands Ctr Wiskunde & Informat Amsterdam Netherlands Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA 

出 版 物：《OPERATIONS RESEARCH LETTERS》 (运筹学快报)

年 卷 期：2014年第42卷第8期

页      面：549-552页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：AFOSR Grant of the Air Force Office of Scientific Research [FA9550-12-1-0151] National Science Foundation [CCF-1415460] Division of Computing and Communication Foundations Direct For Computer & Info Scie & Enginr Funding Source: National Science Foundation 

主　　题：Approximation algorithms Transportation problem with market choice Capacitated facility location 

摘      要：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. Published by Elsevier B.V.