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

2017-11-01 09:47李伟娟陈光亭
关键词:集权子集权重

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

(杭州电子科技大学理学院,浙江 杭州 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

猜你喜欢
集权子集权重
拓扑空间中紧致子集的性质研究
权重常思“浮名轻”
关于奇数阶二元子集的分离序列
为党督政勤履职 代民行权重担当
完全二部图K6,n(6≤n≤38)的点可区别E-全染色
企业集权财务管理模式及其现实选择
基于局部权重k-近质心近邻算法
每一次爱情都只是爱情的子集
集权与分权
组织知识传播与共享评价指标体系及其RS权重配置