Speaker: Wang Changjun, Associate Researcher, Academy of Mathematics and Systems Science, CAS

Date: December 29, 2025

Time: 10:00-11:00 am

Location: Room 310, Office Building, Software Campus, Shandong University

Sponsor: School of Software, Shandong University

Abstract:

We study a new bilevel optimization problem, termed the Randomized Maximum Vertex Cover Interdiction problem under matroid constraints (RMVCI), which can be modeled as a zero-sum Stackelberg game on a network between a leader and a follower. The leader randomly selects a subset of vertices to protect, subject to a matroid constraint, while the follower—after inferring the leader's protection probabilities—chooses a subset of vertices (also matroid-constrained) to attack, aiming to maximize the expected total weight of edges incident to selected and unprotected vertices. The leader's objective is to determine an optimal randomized interdiction strategy that minimizes the follower's expected payoff. Since the follower's response problem is NP-hard, we first introduce a conceptual approximation framework for tackling similar bilevel interdiction problems. Within this framework, we show that the follower's problem in RMVCI can be formulated as an integer linear program whose linear relaxation admits a tight integrality gap of 4/3. For the leader's outer optimization problem—where the inner problem is replaced by its LP relaxation—we further develop a polynomial-time 2-approximation algorithm. By integrating these two components under our framework, we obtain a polynomial-time 8/3-approximation algorithm for the RMVCI. (joint work with Chenhao Wang)

For more information, please visit:

https://view.sdu.edu.cn/info/1020/209238.htm