当前位置: 首页 > 学术报告
学术报告 - 方程方向
Approximation Algorithms for the Constrained Rural Postman Problem on Mixed Graphs
李建平 教授(云南大学数学科学学院)
2018-11-16(周五) 上午10:00-11:00   闵行数学楼126报告厅

报告内容简介:In this talk, we consider the constrained rural postman problem on mixed graphs. We use $Q^+$ and $Z^+$ to denote the sets of positive rational numbers and positive integers, respectively. For any mixed graph $G=(V,E\cup A;w;l,u)$ with two required subsets $E'\subseteq E$ and $A'\subseteq A$, where a length function \map w {E\cup A} {Q^+} and two integer functions \map {l,u} {E'\cup A'} {Z^+}, satisfying $l(e) \leq u(e)$ for each edge $e\in E'\cup A'$, we are asked to determine a minimum length tour $C$ traversing each edge $e\in E'\cup A'$ at least $l(e)$ and at most $u(e)$ times.Our main results are as follows. (1) We present a few facts that they are {\it NP}-hard to determine feasible tours for the constrained rural postman problem specialized on digraphs for some special cases. (2) We design a $3$-approximation algorithm to solve this problem specialized on graphs. This work is jointed with Xiaofei Liu.

主持人:吕长虹 教授