限制性最短路构建问题  

The Problem of Constructing Restricted Shortest Path

作　　者：丁红林 李建平[1] DING Honglin;LI Jianping(School of Mathematics and Statistics,Yunnan University,Kunming 650504)

机构地区：[1]云南大学数学与统计学院,昆明650504

出　　处：《系统科学与数学》2023年第7期1837-1848,共12页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金项目(11861075,11801498);云南省科技创新团队培育项目(202005AE160006);云南省科技厅科研项目(202001BB050062)资助课题。

摘　　要：文章研究限制性最短路和装箱的一种组合问题.设赋权有向图D=(V,A;s,t;w,c),其中w:A→R^(+)为长度函数,c:A→R_(0)^(+)为构建费用函数,s,t为两个固定顶点.给定一些长度为L的材料,每根材料的购买费用为c0,B是一个常数.要在有向图D中寻找一条s-t路P,其总长度满足要求∑_(e∈P) w(e)≤B,并使用长度为L的材料来构建路P上的所有弧,目标为使得总费用∑_(e∈P)c(e)+k(P)c_(0)达到最小,其中k(P)表示构建路P上的所有弧需要使用的材料根数.文章设计了一个7(1+ε)/4-渐进近似算法求解该问题,该算法的时间复杂度为O(mn(log logn+1/ε)),这里ε> 0为任意常数,n与m分别表示有向图D中的顶点数和弧数.文章进一步研究了该问题在构建费用函数恒为0的特殊情形,等价地,目标函数是使得需要使用的材料根数达到最小,并设计了一个3/2-渐进近似算法求解该特殊情形,新算法的时间复杂度为O(n^(2)).In this paper,we consider a combination problem of restricted shortest path and bin packing,which is defined as follows.Given a weighted digraph D=(V,A,s,t;w,c),where w:A→R~+ is a length function,c:A→R_0~+ is a construction cost function,and s,t ∈ V are two fixed vertices,there are some stock pieces with fixed length L and a price c_(0) for per stock piece,and a constant bound B.We are asked to find a path P from s to t in D such that the total length of P satisfies a requirement ∑_(e∈P)w(c) ≤ B,and all arcs in P are further asked to be constructed by using some stock pieces with fixed length L.The objective is to minimize the total cost∑_(e∈P) c(e)+ k(P)c_0,where k(P) denotes the number of necessary stock pieces with fixed length L to construct all arcs in P.We design an asymptotic7(1 +ε)/4-approximation algorithm to solve this problem,and this algorithm runs in time O(mn(log logn+ 1/ε)),where ε 0 is an arbitrary constant,n and m represent the numbers of vertices and arcs in D,respectively.Moreover,we consider its special version,where c(e)=0 holds for each arc e in D,equivalently,the objective is to minimize the number of such stock pieces used.We provide an asymptotic 3/2-approximation algorithm in time O(n~2) to solve this special version.

关 键 词：网络构建 限制性最短路 装箱 近似算法 复杂性 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]