In this paper,we address the k-Chinese postman problem under interdiction budget constraints(the k-CPIBC problem,for short),which is a further generalization of the k-Chinese postman problem and has many practical app...In this paper,we address the k-Chinese postman problem under interdiction budget constraints(the k-CPIBC problem,for short),which is a further generalization of the k-Chinese postman problem and has many practical applications in real life.Specifically,given a weighted graph G=(V,E;w,c;v_(1))equipped with a weight function w:E→R^(+)that satisfies the triangle inequality,an interdiction cost function c:E→Z^(+),a fixed depot v_(1)∈V,an integer k∈^Z^(+)and a budget B∈N,we are asked to find a subset S_(K)■E such that c(S_(K))=∑_(e∈S_(k)c_(e))≤B and that the subgraph G\S_(k)is connected,the objective is to minimize the value min_(C_(E)\S_(k))max{w(C_(i))|C_(i)∈C_(E)\S_(K)}among such all aforementioned subsets S_(k),where C_(E)S_(k)is a set of k-tours(of G\S_(k))starting and ending at the depot v_(1),jointly traversing each edge in G\S_(k)at least once,and w(C_(i))=∑e∈C_(i)w(e)for each tour C_(i)∈C_(E)\S_(k).We obtain the following main results:(1)Given an-approximation algorithm to solve the minimization knapsack problem,we design an(α+β)-approximation algorithm to solve the k-CPIBC problem,whereβ=7/2-1/k-[1/k].(2)We present aβ-approximation algorithm to solve the special version of the k-CPIBC problem,where c(e)1 for each edge e in G and is defined in(1).展开更多
We address the 1-line minimum Steiner tree of line segments(1L-MStT-LS)problem.Specifically,given a set S of n disjoint line segments in R^(2),we are asked to find the location of a line l and a set E_(l) of necessary...We address the 1-line minimum Steiner tree of line segments(1L-MStT-LS)problem.Specifically,given a set S of n disjoint line segments in R^(2),we are asked to find the location of a line l and a set E_(l) of necessary line segments(i.e.,edges)such that a graph consisting of all line segments in S ∪ E_(l) plus this line l,denoted by T_(l)=(S,l,E_(l)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(l) among all such Steiner trees.Similarly,we are asked to find a set E_(0) of necessary edges such that a graph consisting of all line segments in S ∪ E_(0),denoted by T_(S)=(S,E_(0)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(0) among all such Steiner trees,we refer to this new problem as the minimum Steiner tree of line segments(MStT-LS)problem.In addition,when two endpoints of each edge in Eo need to be located on two different line segments in S,respectively,we refer to that problem as the minimum spanning tree of line segments(MST-LS)problem.We obtain three main results:(1)Using technique of Voronoi diagram of line segments,we design an exact algorithm in time O(n log n)to solve the MST-LS problem;(2)we show that the algorithm designed in(1)is a 1.214-approximation algorithm to solve the MStT-LS problem;(3)using the combination of the algorithm designed in(1)as a subroutine for many times,a technique of finding linear facility location and a key lemma proved by techniques of computational geometry,we present a 1.214-approximation algorithm in time O(n^(3) log n)to solve the 1L-MStT-LS problem.展开更多
In this paper,we address the problem of constructing a Steiner tree in the Euclidean plane R^(2)using stock pieces of materials with fixed length,which is modelled as follows.Given a set X={r_(1),r_(2)…,r_(n)}of n te...In this paper,we address the problem of constructing a Steiner tree in the Euclidean plane R^(2)using stock pieces of materials with fixed length,which is modelled as follows.Given a set X={r_(1),r_(2)…,r_(n)}of n terminals in R^(2)and some stock pieces of materials with fixed length L,we are asked to construct a Steiner tree T interconnecting all terminals in X,and each edge in T must be constructed by a part of that stock piece of material.The objective is to minimize the cost of constructing such a Steiner tree T,where the cost includes three components,(1)The cost of Steiner points needed in T;(2)The construction cost of constructing all edges in T and(3)The cost of stock pieces of such materials used to construct all edges in T.We can obtain two main results.(1)Using techniques of constructing a Euclidean minimum spanning tree on the set X and a strategy of solving the bin-packing problem,we present a simple 4-approximation algorithm in time O(n log n)to solve this new problem;(2)Using techniques of computational geometry to solve two nonlinear mathematical programming to obtain a key Lemma 8 and using other strategy of solving the bin-packing problem,we design a 3-approximation algorithm in time O(n^(3))to resolve this new problem.展开更多
基金supported by the National Natural Science Foundation of China(Nos.11861075,12101593)Project for Innovation Team(Cultivation)of Yunnan Province(No.202005AE-160006)+2 种基金Peng-Xiang Pan is also supported by Project of Yunnan Provincial Department of Education Science Research Fund(No.2020Y0040)Jun-Ran Lichen is also supported by Fundamental Research Funds for the Central Universities(No.buctrc202219)Jian-Ping Li is also supported by Project of Yunling Scholars Training of Yunnan Province(No.K264202011820).
文摘In this paper,we address the k-Chinese postman problem under interdiction budget constraints(the k-CPIBC problem,for short),which is a further generalization of the k-Chinese postman problem and has many practical applications in real life.Specifically,given a weighted graph G=(V,E;w,c;v_(1))equipped with a weight function w:E→R^(+)that satisfies the triangle inequality,an interdiction cost function c:E→Z^(+),a fixed depot v_(1)∈V,an integer k∈^Z^(+)and a budget B∈N,we are asked to find a subset S_(K)■E such that c(S_(K))=∑_(e∈S_(k)c_(e))≤B and that the subgraph G\S_(k)is connected,the objective is to minimize the value min_(C_(E)\S_(k))max{w(C_(i))|C_(i)∈C_(E)\S_(K)}among such all aforementioned subsets S_(k),where C_(E)S_(k)is a set of k-tours(of G\S_(k))starting and ending at the depot v_(1),jointly traversing each edge in G\S_(k)at least once,and w(C_(i))=∑e∈C_(i)w(e)for each tour C_(i)∈C_(E)\S_(k).We obtain the following main results:(1)Given an-approximation algorithm to solve the minimization knapsack problem,we design an(α+β)-approximation algorithm to solve the k-CPIBC problem,whereβ=7/2-1/k-[1/k].(2)We present aβ-approximation algorithm to solve the special version of the k-CPIBC problem,where c(e)1 for each edge e in G and is defined in(1).
基金supported by the National Natural Science Foundation of China(Nos.11861075 and 12101593)Project for Innovation Team(Cultivation)of Yunnan Province(No.202005AE160006)+2 种基金Key Project of Yunnan Provincial Science and Technology Department and Yunnan University(No.2018FY001014)Program for Innovative Research Team(in Science and Technology)in Universities of Yunnan Province(No.C176240111009)Jian-Ping Li is also supported by Project of Yunling Scholars Training of Yunnan Province.Su-Ding Liu is also supported by the Graduate Research and Innovation Project of Yunnan University(No.2020Z66).
文摘We address the 1-line minimum Steiner tree of line segments(1L-MStT-LS)problem.Specifically,given a set S of n disjoint line segments in R^(2),we are asked to find the location of a line l and a set E_(l) of necessary line segments(i.e.,edges)such that a graph consisting of all line segments in S ∪ E_(l) plus this line l,denoted by T_(l)=(S,l,E_(l)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(l) among all such Steiner trees.Similarly,we are asked to find a set E_(0) of necessary edges such that a graph consisting of all line segments in S ∪ E_(0),denoted by T_(S)=(S,E_(0)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(0) among all such Steiner trees,we refer to this new problem as the minimum Steiner tree of line segments(MStT-LS)problem.In addition,when two endpoints of each edge in Eo need to be located on two different line segments in S,respectively,we refer to that problem as the minimum spanning tree of line segments(MST-LS)problem.We obtain three main results:(1)Using technique of Voronoi diagram of line segments,we design an exact algorithm in time O(n log n)to solve the MST-LS problem;(2)we show that the algorithm designed in(1)is a 1.214-approximation algorithm to solve the MStT-LS problem;(3)using the combination of the algorithm designed in(1)as a subroutine for many times,a technique of finding linear facility location and a key lemma proved by techniques of computational geometry,we present a 1.214-approximation algorithm in time O(n^(3) log n)to solve the 1L-MStT-LS problem.
基金supported by the National Natural Science Foundation of China(Nos.11861075 and 12101593)Project for Innovation Team(Cultivation)of Yunnan Province(No.202005AE160006)+1 种基金supported by Fundamental Research Funds for the Central Universities(No.buctrc202219)supported by Project of Yunling Scholars Training of Yunnan Province(No.K264202011820).
文摘In this paper,we address the problem of constructing a Steiner tree in the Euclidean plane R^(2)using stock pieces of materials with fixed length,which is modelled as follows.Given a set X={r_(1),r_(2)…,r_(n)}of n terminals in R^(2)and some stock pieces of materials with fixed length L,we are asked to construct a Steiner tree T interconnecting all terminals in X,and each edge in T must be constructed by a part of that stock piece of material.The objective is to minimize the cost of constructing such a Steiner tree T,where the cost includes three components,(1)The cost of Steiner points needed in T;(2)The construction cost of constructing all edges in T and(3)The cost of stock pieces of such materials used to construct all edges in T.We can obtain two main results.(1)Using techniques of constructing a Euclidean minimum spanning tree on the set X and a strategy of solving the bin-packing problem,we present a simple 4-approximation algorithm in time O(n log n)to solve this new problem;(2)Using techniques of computational geometry to solve two nonlinear mathematical programming to obtain a key Lemma 8 and using other strategy of solving the bin-packing problem,we design a 3-approximation algorithm in time O(n^(3))to resolve this new problem.
