题  目：Maximumb-matching based approximation algorithm design

基于最大b-匹配的近似算法设计

报告人：Guohui Lin教授，Universityof Alberta

时  间：2017年6月20日（星期二）上午10:00-12:00

地  点：西安交通大学管理学院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.

欢迎广大师生参加！

管理学院

2017年6月14日