2014年4月14日，北京工业大学徐大川教授来我校进行招生宣传并作学术报告。

4月14日下午3:00—4:00，招生宣传。听众对象：二三年级本科生。

4月14日下午4:00—5:00，学术讲座。听众对象：图论与组合最优化方向教师研究生。

讲学题目：Primal-dual approximation algorithms for submodular vertex cover problems with linear/submodular penalties

讲学摘要：The vertex cover problem is a fundamental and widely investigated problem in combinatorial optimization. A vertex coverproblem is defined on an undirected graph where each vertex is associated with a cost. A vertex subset is called a vertexcover if each edge is incident to at least one vertex in the subset---that is, the vertex subset covers all the edges. Theobjective is to find a vertex cover with minimum total cost. The classical vertex cover problem was extended to thesubmodular case (Iwata and Nagano, FOCS 2009), where, given a nonnegative submodular function defined on each subset of thevertex set, the objective is to find a vertex cover that minimizes the total cost. In this work, we relax further therequirement that a vertex cover has to cover all the edges by penalizing the uncovered edges, resulting in the submodularvertex cover problem with penalties (SVCWP). We consider two variants depending on whether the penalty cost function islinear or submodular, namely the submodular vertex cover problem with linear penalties (SVCLP) and the submodular vertex cover problemwith submodular penalties (SVCSP).

We present two primal-dual approximation algorithms with approximation ratios of 2 and 4 for the SVCLP and SVCSP, respectively.Implementing the primal-dual framework directly on the dual programs of the linear program relaxations for the SVCLP and SVCSP cannotguarantee the dual ascending process terminates in polynomial time. To overcome this difficulty, we relax these two dual programs toslightly weaker versions which lead to two primal-dual approximation algorithms with the claimed approximation ratios.

(Joint work with Fengmin Wang, Donglei Du, and Chenchen Wu)