丁红林, 李建平
文章研究限制性最短路和装箱的一种组合问题.设赋权有向图$D$=$(V,A;s,t;w,c)$, 其中,$w:A\rightarrow{R^+}$,为长度函数, $c:A\rightarrow {R^+_0}$,为构建费用函数,$s,t$,为两个固定顶点. 给定一些长度为,$L$,的材料,每根材料的购买费用为,$c_0$, $B$,是一个常数.要在有向图$D$,中寻找一条$s-t$路$P$,其总长度满足要求,$\sum_{e\in P} w(e)\leq B$,并使用长度为$L$的材料来构建路$P$上的所有弧,目标为使得总费用$\sum_{e\in P}c(e)$ $+$ $k(P)c_0$,达到最小,其中,$k(P)$,表示构建路$P$上的所有弧需要使用的材料根数.文章设计了一个$7(1+epsilon)/4$-渐进近似算法求解该问题,该算法的时间复杂度为${\mathcal O}(mn(\log\log n+1/\epsilon))$,这里$\epsilon>0$,为任意常数,$n$与$m$分别表示有向图$D$,中的顶点数和弧数.文章进一步研究了该问题在构建费用函数恒为0的特殊情形,等价地,目标函数是使得需要使用的材料根数达到最小,并设计了一个,$3/2$-渐进近似算法求解该特殊情形,新算法的时间复杂度为,${\mathcal O}(n^2)$.
