报告题目：Lower Bounds for the Weighted Max Cut Problem
报 告 人：Gregory Gutin（伦敦大学皇家霍洛威学院 教授）
报告时间：2022年4月13日 下午16:00开始
报告地点：腾讯会议线上报告
会议链接：//meeting.tencent.com/dm/jefJEGSnZFqM
会议ID： 674-756-416
报告摘要： While there have been many results on lower bounds for Max Cut in unweighted graphs, the only lower bound for non-integer weights is that by Poljak and Turzik (1986). We'll discuss an extensive study of lower bounds for Max Cut in weighted graphs. We'll introduce a new approach for obtaining lower bounds for Weighted Max Cut. Using it, Probabilistic Method, Vizing's chromatic index theorem, and other tools, we can obtain several lower bounds for arbitrary weighted graphs, weighted graphs of bounded girth and triangle-free weighted graphs. We'll pose conjectures and open questions.
报告人简介：Gregory Gutin，伦敦大学皇家霍洛威学院教授，欧洲科学院院士，亚太人工智能学会会士。1993年博士毕业于以色列特拉维夫大学，师从 Noga Alon教授。主要研究方向为图论、算法设计与分析、信息安全、组合优化及应用、理论经济学。担任Discrete Optimization等期刊编委。出版学术著作3部，发表学术论文250多篇，论著被引用次数超过11300次，H-指数41。
