报告题目 (Title)：A bridge between the coin-weighing problem and the double resolving problem of graphs(硬币称重问题与图的2-分辨集问题之间的桥梁)
报告人 (Speaker)： 吕长虹 教授（华东师范大学）
报告时间 (Time)：2021年11月18日(周四) 16:30
报告地点 (Place)：腾讯会议 会议ID：873 777 5758
邀请人(Inviter)：王文环 康丽英 袁西英
报告摘要：硬币称重问题（Coin-weighing problems）是个经典的组合优化问题，其中一个经典形式为：给定n个硬币，假定真硬币的重量和假硬币的重量均已知，用弹簧称对硬币进行称重，用最少的称重次数将所有的假币找出来。图的2-分辨集（double resolving problem）是Caceres 等人在2007年为了研究图的分辨集问题（resolving set problem）提出的一个工具性的新概念。最近，我们证明了超方体的2-分辨集问题与硬币称重问题的等价关系，我们利用硬币称重问题的Lindström方法给出计算超方体和折叠超方体2-分辨集问题的快速算法，给出了一些新结果，包括解决公开问题；反过来，2-分辨集问题的图论结果也给硬币称重问题带来了一些新进展，比如14,16,18个硬币称重问题的新上界。