二部图中的完美匹配子集权的极小化问题

李伟娟，陈光亭，陈 永，张 安

(杭州电子科技大学理学院，浙江 杭州 310018)

二部图中的完美匹配子集权的极小化问题

李伟娟，陈光亭，陈 永，张 安

(杭州电子科技大学理学院，浙江 杭州 310018)

主要研究了二部图中的完美匹配子集权的极小化问题，针对完美匹配两个子集权的极小化问题，证明了最小权重优先算法SWF的最坏情况界为3/2，并应用一一互换思想，设计了最坏情况界至多为4/3的改进算法.

二部图；完美匹配；近似算法；最坏情况界

0 引 言

1 问题陈述及符号说明

图1 问题示意图

2 近似算法及最坏情况分析

最小权重优先(Smallest Weight First, SWF)算法的基本步骤如下：

1)将权重按照从小到大的顺序排序w(e1)≤w(e2)≤…≤w(e2n)；

2)从权重最小的边开始，依次放入当前边权和最小的子集U1或者U2里.

引理按照SWF算法，最终得到2个集合U1和U2里边的条数一定相等.

证明反证法.若集合U1和U2里边的个数不相等，一定存在一条边em,不妨设em在U2，在em放入U2之前，记w(U2)=sm，w(U1)=r分别表示子集U2，U1的权重，则有

sm+w(em)

(1)

定理1SWF算法的最坏情况界不超过3/2且是紧的.

证明记M1为SWF算法得到的完美匹配，设边权w(e2n)放入子集U2时，U2中的边权和记为s2n，则有

实例说明3/2的界是紧的.Ui=2(i=1,2),U1有2个点u1，u2.U2有2个点u3,u4.V=4，V中有4个点v1，v2，v3，v4.各边的权重分别为：

w(e1)=w(v1,u1)=w(v1,u3)=ε,w(e2)=w(v2,u2)=w(v2,u4)=1,w(e3)=w(v3,u3)=w(v3,u1)=1,w(e4)=w(v4,u4)=w(v4,u2)=2.

图2 最优解

图3 算法解

下面给出改进的一一互换算法.令U1，U2是e1，e2，…，e2n的一个划分且Ui=n(i=1,2)，不妨假设w(Uq)er，Uq=Uq∪eres，称为一次一一互换.易知，互换后的匹配最大权只可能减少.

互换算法的步骤如下：

1)将U任意划分成边数相等的两个子集Ui(i=1,2)；

2)不断进行上述的一一互换过程，直至不能进行互换为止.

定理2互换算法的最坏情况界至多是4/3.

证明记M2为互换算法得到的完美匹配，假定w(M*)=1(w(ei)除以w(M*)).因此对于划分U1，U2有

(2)

假设w(U1)=1+α且w(U1)是子集中权和最大者，w(U2)是子集中权和较小者.记Δ12=w(U1)-w(U2)，δ12=minw(er)-w(es)|w(er)-w(es)>0，er∈U1，es∈U2若U1，U2已不能进行一一互换了，那么Δ12≤δ12，根据式(2)可得

Δ12=w(U1)-w(U2)=2w(U1)-(w(U1)+w(U2))≥2(1+α)-2=2α.

3 结束语

本文主要研究了二部图中的完美匹配子集权的极小化问题，首先设计了最小权重优先算法并证明了算法的最坏情况界为3/2且是紧的.其次，根据一一互换思想，设计的改进算法的最坏情况界至多为4/3.下一步将对集合U的个数m>2的情况做进一步研究.

[1] BARKETAU M, PESCH E, SHAFRANSKY Y. Minimizing maximum weight of subsets of a maximum matching in a bipartite graph[J]. Discrete Applied Mathematics, 2015,196:4-19.

[2] BOYSEN N, FLIEDNER M. Determining crane areas in intermodal transshipment yards: The yard partition problem[J]. European Journal of Operational Research, 2010,204(2):336-342.

[3] BOYSEN N, FLIEDNER M, JAEHN F, et al. A survey on container processing in railway yards[J]. Transportation Science, 2013,47(3):312-329.

[4] BURKARD R E, DELL’AMICO M, MARTELLO S. Assignment Problems, Revised Reprint[M]. Philadelphia: Society for Industrial and Applied Mathematics, 2009:383-386.

[5] PAPADIMITRIOU C H, STEIGLITZ K. Combinatorial optimization: algorithms and complexity[M]. Englewood:Prentice-Hall, 1982:495-496.

[6] CARPANETO G, TOTH P. Algorithm for the solution of the bottleneck assignment problem[J]. Computing, 1981,27(2):179-187.

[7] FUJITO T, NAGAMOCHI H. A 2-approximation algorithm for the minimum weight edge dominating set problem[J]. Discrete Applied Mathematics, 2002,118(3):199-207.

MinimizingMaximumWeightofSubsetsofaPerfectMatchinginaBipartiteGraph

LI Weijuan, CHEN Guangting, CHEN Yong, ZHANG An

(SchoolofScience,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

This paper studies the minimization problem of perfect matching subset weights in bipartite graphs. It first proves that the worst case ratio of the SWF algorithm is 3/2, and then an improved algorithm using the one to one exchange idea is presented, which is shown to be 4/3-approximation.

bipartite graph; perfect matching; approximation algorithm; worst-case ratio

O221.7

A

1001-9146(2017)05-0097-03

2016-12-05

国家自然科学基金资助项目(11571252，11401149)；浙江省自然科学基金资助项目(LY16A010015)

李伟娟(1989-)，女，河南荥阳市人，硕士研究生，组合优化.通信作者：陈光亭教授，E-mail：gtchen@hdu.edu.cn.

10.13954/j.cnki.hdu.2017.05.018