題  目：Maximumb-matching based approximation algorithm design

基于最大b-匹配的近似算法設(shè)計(jì)

報(bào)告人：Guohui Lin教授，Universityof Alberta

時(shí)  間：2017年6月20日（星期二）上午10:00-12:00

地  點(diǎn)：bwin必贏唯一官網(wǎng)315

A classic use of amaximum weight matching in approximating the traveling salesman problem leadsto the 1.5-approximation algorithm in 1976. The maximum b-matchings, weighted and unweighted, have also beenemployed in the design of approximation algorithms for the maximum travelingsalesman problem, with its most recent ratio of 0.8 achieved by Dudyez et al.(2015), and many other problems.  In thistalk, we will present another use of the maximum b-matchings in approximatingthe Bandpass problem, which is formulated out of the optical communicationnetworks.  To the end, we show that amaximum weight matching, a maximum weight 2-matching, and a maximum weight4-matching can be used together to design a 13/24-approximation algorithm forthe Bandpass problem.

歡迎廣大師生參加！

bwin必贏唯一官網(wǎng)

2017年6月14日