A bridge between the coin-weighing problem and the minimal doubly resolving set problem in graphs
报告题目(Title)：A bridge between the coin-weighing problem and the minimal doubly resolving set problem in graphs
报告人(Speaker)：吕长虹 教授 (华东师范大学)
地点(Place)：腾讯会议：774 373 704
时间(Time)：2021-5-28, 下午 3:00-4:00.
邀请人(Inviter)：徐敏
报告摘要
硬币称重问题（Coin-weighing problem）是一个经典的组合优化问题：给定n个硬币，假定真硬币的重量和假硬币的重量均已知，现在需要制定一个称重策略，能用最少的称重次数将所有的假币找出来。硬币称重问题得到Erdos、Renyi、Lindstrom等在内的很多学者的研究。图的2-分辨集（Double resolving set）是Caceres 等人为了研究图的维数在2007年才提出的一个工具性的新概念。最近，我和博士生叶青杰发现了图的2-分辨集问题与硬币称重问题的存在紧密联系。我们利用硬币称重问题上著名的Lindstrom方法解决了图的2-分辨集问题上的猜想，并给出了计算超方体和折叠超方体2-分辨集问题的快速算法。另一方面，2-分辨集问题的图论结果反过来也提供了硬币称重问题的一些新进展。
主讲人简介
吕长虹，华东师范大学数学科学学院教授，博士生导师，主要从事图论和组合算法方面理论和应用研究，在SIAM J. Disc. Math、Disc、Math、Disc. Appl. Math、European J. Comb.等期刊发表论文40余篇，申请发明专利4项，授权发明专利1项。2012年入选教育部新世纪优秀人才计划，2020年获得上海市科技进步特等奖和第二届萧树铁应用数学奖。现为中国数学会常务理事、上海市工业与应用数学学会副理事长、上海市运筹学会副理事长。
