首届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）于2020年8月17日-22日在线上举行，主题为“理论计算机科学领域的最新进展与焦点问题”，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办。  

　　8月17日，大会“算法与复杂性”分论坛如期举行，由香港城市大学李闵溟教授主持。小编为大家带来论坛精彩回顾。

Defending with Shared Resources on a Network
李闽溟，香港城市大学

　　作者考虑了一个新颖的网络上的防守问题，其背景为在城市的各个地区分配安保资源。该问题可形式化为一具有边权的网络，边权代表各地区之间共享安保资源的效率；有限的资源分配到每个顶点上，其实际享有的安保资源等于其本身拥有的资源与经效率加权后邻接点的资源和；受到攻击时，每个点有一完好无损的阈值 UB 和被攻陷的阈值 LB，根据攻击强度和安保资源，最后存在不同程度的损失，需要对资源进行合理分配，使得损失最小。

　　对于这个问题，作者对 UB=LB 的二元情形以及各点之间不存在资源共享的情形进行了研究，分别通过构造 LP 和网络流问题，在多项式时间内求解之。随后，作者通过从 MAX-CNF 进行归约，证明了一般情形的网络上的防守问题是 NP-Hard 的。由此结果，作者还进一步利用对 LP 的松弛，设计了一个有效的2-近似算法。