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

摘要：

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

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

所属期刊栏目：39

分类号：TP39(计算技术、计算机技术)

在线出版日期：2013-08-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：305-308