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

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

作　　者：王刚[1] 骆志刚[1] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073

出　　处：《计算机工程》2013年第4期305-308,共4页Computer Engineering

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

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

分 类 号：TP39[自动化与计算机技术—计算机应用技术]