Total Dual Integrality in Some Facility Location Problems
Total Dual Integrality in Some Facility Location Problems
复制标题
一些设施选址问题的完全对偶完整性
DOI：
10.1137/090768400
复制
发表时间：
2012-07
影响因子：
0.8
通讯作者：
Wenan Zang
中科院分区：
文献类型：
--
作者：
Xujin CHEN;陈智斌;Wenan Zang
设施选址问题在运筹学和计算机科学领域有着广泛的应用。本文研究了经典的无容量限制的设施选址问题及其由Baiou和Barahona提出的“奖品收集”问题，证明了与这类问题相关的线性系统是完全对偶积分的当且仅当输入图中不含某种类型的奇圈.作为推论，我们得到了设施选址的两个极大极小关系的结构特征。我们的结果加强了Baiou和Barahona证明的设施选址多面体的完整性定理;我们的证明导致了我们考虑的设施选址问题的组合多项式时间算法。
Facility location, arising in a rich variety of applications, has been studied extensively in the fields of operations research and computer science. In this paper we consider the classical uncapacitated facility location problem and its "prize-collecting" variant introduced by Ba¨ iou and Barahona, and we show that the linear systems associated with these problems are totally dual integral if and only if the input graphs do not contain a certain type of odd cycles. As corollaries, we get structural characterizations of two min-max relations on facility location. Our results strengthen the integrality theorems on facility location polytopes proved by Ba¨ iou and Barahona; our proofs lead to combinatorial polynomial-time algorithms for the facility location problems that we consider.
登录
查看更多内容
DOI：
10.1007/978-0-387-30162-4_28
发表时间：
2021-08
期刊：
Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN'97)
影响因子：
--
作者：
通讯作者：
--
影响因子：
3.6
作者：
Sushil K. Gupta
通讯作者：
Sushil K. Gupta
DOI：
10.1109/sfcs.1980.27
发表时间：
1980-10
期刊：
21st Annual Symposium on Foundations of Computer Science (sfcs 1980)
影响因子：
--
作者：
M. Yannakakis
通讯作者：
M. Yannakakis
影响因子：
2.1
作者：
Frederic G. Commoner
通讯作者：
Frederic G. Commoner
DOI：
10.1145/375827.375845
发表时间：
2001-03
期刊：
J. ACM
影响因子：
--
作者：
K. Jain;V. Vazirani
通讯作者：
K. Jain;V. Vazirani