讲座题目:Maximumb-matching based approximation algorithm design

题  目:Maximumb-matching based approximation algorithm design


报告人: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.