计算机工程 ›› 2013, Vol. 39 ›› Issue (4): 305-308.doi: 10.3969/j.issn.1000-3428.2013.04.070

• 开发研究与工程应用 • 上一篇    下一篇

制服调换问题中的路圈子图与圈包装研究

王 刚,骆志刚   

  1. (国防科学技术大学计算机学院,长沙 410073)
  • 收稿日期:2012-04-24 出版日期:2013-04-15 发布日期:2013-04-12
  • 作者简介:王 刚(1978-),男,博士研究生,主研方向:近似算法,资源调度;骆志刚,研究员、博士、博士生导师

Study of Path-cycle Subgraph and Cycle Packing in Uniform Exchange Problem

WANG Gang, LUO Zhi-gang   

  1. (College of Computer, National University of Defense Technology, Changsha 410073, China)
  • Received:2012-04-24 Online:2013-04-15 Published:2013-04-12

摘要: 利用制服型号数有限这一特征,对制服调换(UE)问题和以物易物的制服调换(BUE)问题各给出一个快速的线性时间算法。在常量阶有向图上,将BUE转化为一个顶点容量约束的整值最大环流问题,提出其整数线性规划表示,论证其可行域的整性。证明BUE的最优解必为对应UE的一个最优解子图。实验结果表明,UE和BUE的渐进最优值相同。

关键词: 制服调换, 路圈子图, 圈包装, 环流, 线性规划松弛

Abstract: Utilizing the finiteness of the uniform type number, this paper presents faster linear time algorithms for the Uniform Exchange(UE) problem and the Barter Uniform Exchange(BUE) problem. BUE is Transfered into a vertex constraint integer value maximum circulation problem on a constant order digraph, and the integrality of the feasible region of BUE’s integer linear programming formulation is proved. It is demonstrated that any optimal solution to BUE must be a subgraph of some optimal solution to the corresponding UE, and experimental results show that the two problems share a same asymptotical optimal values.

Key words: Uniform Exchange(UE), path-cycle subgraph, cycle packing, circulation, linear programming relaxation

中图分类号: