We study a bilevel combinatorial optimization problem,termed the Randomized Max-Vertex-Coverage Interdiction(RMVCI)problem under matroid constraints,which can beviewed as a zero-sum Stackelberg game on a network.The leader randomly selects amatroid-feasible subset of vertices to protect,while the follower—after inferring thisdistribution-chooses a matroid-feasible subset to attack,aiming to maximize theexpected weight of edges incident to vertices that are both attacked and unprotected.Theleader seeks an optimal randomized strategy minimizing this expected payoff.
As the follower s problem is NP-hard,the bilevel program is computationally challenging.We develop a general approximation framework for such interdiction problems.For RMVCIunder matroid constraint,we formulate the follower's problem as an ILP and show its LPrelaxation has a tight integrality gap of 4/3.Replacing the follower's problem with thisrelaxation and shifting from distributions over sets to distributions over vertices,we obtaina polynomial-time 2-approximation for the relaxed bilevel problem.Combining theseresults yields a polynomial-time 8/3-approximation algorithm for RMVCI under matroidconstraints.(joint work with Chenhao Wang)
 

王长军，现任中国科学院数学与系统科学研究院副研究员。主要从事算法博弈与机制设计、组合优化等方向的理论与应用研究。目前已在包括OR、MS、MOR、EC、WINE等的相关领域重要国际期刊及会议发表多篇论文。曾主持国家自然科学基金面上项目、中国科协青年人才托举工程项目及获中国运筹学会青年科技奖等。