二部圖中的完美匹配子集權的極小化問題

李偉娟，陳光亭，陳 永，張 安

(杭州電子科技大學理學院，浙江 杭州 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