报告人：操宜新 副教授 香港理工大学

报告题目I：Half-integral Solutions of Linear Systems

报告时间：2026年5月17日 9:00-9:50

报告地点：炸金花 301室

摘要： Most combinatorial optimization problems are NP-hard, which means their integer programming formulations typically lack the total dual integrality property. In the 1970s, Balinski observed that all extreme points of the fractional independent set polytope are half-integral. In this work, we explore further developments in this area. Additionally, we provide a brief discussion on employing graph-theoretical approaches to solve integer programs.

报告题目II：Cluster Vertex Deletion on Chordal Graphs

报告时间：2026年5月17日 10:00-10:50

报告地点：炸金花 301室

摘要：In the cluster vertex deletion problem, we are given a vertex-weighted graph and asked to delete a minimum-weight set of vertices so that the resulting graph is a cluster graph (a graph whose components are all cliques). We present a polynomial-time algorithm for this problem on chordal graphs, resolving an open question posed in different contexts by Cao et al.~[Theoretical Computer Science, 2018], Aprile et al.~[Mathematical Programming, 2023], and Hsieh et al.~[Algorithmica, 2024]. We use dynamic programming over clique trees and reduce the computation of the optimal subproblem value to the minimization of a submodular set function.

报告人简介：操宜新博士是香港理工大学计算学系的副教授，2012年博士毕业于德州农机大学。在2014年回国之前，他在匈牙利科学院做了两年的研究员。他的研究兴趣包括算法图论，细粒度复杂性和算法设计，组合优化。他的研究得到了香港研究资助委员会（RGC）和国家自然科学基金（NSFC）的支持。目前主要学术兼职包括中国计算机学会理论计算机科学专业委员会常务委员和中国运筹学会数学规划分会理事和图论组合分会理事。