期刊文献+
任意字段
题名或关键词
题名
关键词
摘要
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到3篇文章
< 1 >
每页显示 20 50 100
已选0条
引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
Approximation Algorithms for Solving the k-Chinese Postman Problem Under Interdiction Budget Constraints 认领 引用
1
作者 Peng-Xiang Pan Jun-Ran Lichen +2 位作者 Wen-Cheng Wang Li-Jian Cai Jian-Ping Li 《Journal of the Operations Research Society of China》 EI CSCD 2025年第2期535-554,共20页
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;v1)equipped with a weight function w:E→R+that satisfies the triangle inequality,an interdiction cost function c:E→Z+,a fixed depot v1∈V,an integer k∈^Z+and a budget B∈N,we are asked to find a subset SK■E such that c(SK)=∑e∈S_(kce)≤B and that the subgraph G\Skis connected,the objective is to minimize the value minC_(E\Sk)max{w(Ci)|Ci∈CE\SK}among such all aforementioned subsets Sk,where CESkis a set of k-tours(of G\Sk)starting and ending at the depot v1,jointly traversing each edge in G\Skat least once,and w(Ci)=∑e∈Ciw(e)for each tour Ci∈CE\Sk.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). 展开更多
关键词 Combinatorial optimization Arc routing k-Chinese postman problem Interdiction Approximation algorithms
Approximation Algorithms for Solving the 1-Line Minimum Steiner Tree of Line Segments Problem 认领 引用
2
作者 Jian-Ping Li Su-Ding Liu +2 位作者 Jun-Ran Lichen Peng-Xiang Pan Wen-Cheng Wang 《Journal of the Operations Research Society of China》 EI CSCD 2024年第3期729-755,共27页
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 R2,we are asked to find the location of a line l and a set El 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 R2,we are asked to find the location of a line l and a set El of necessary line segments(i.e.,edges)such that a graph consisting of all line segments in S ∪ El plus this line l,denoted by Tl=(S,l,El),becomes a Steiner tree,the objective is to minimize total length of edges in El among all such Steiner trees.Similarly,we are asked to find a set E0 of necessary edges such that a graph consisting of all line segments in S ∪ E0,denoted by TS=(S,E0),becomes a Steiner tree,the objective is to minimize total length of edges in E0 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(n3 log n)to solve the 1L-MStT-LS problem. 展开更多
关键词 1-Line minimum Steiner tree of line segments Minimum spanning tree of line segments Voronoi diagram of line segments Steiner ratio Approximation algorithms
Approximation Algorithms for Constructing Steiner Trees in the Euclidean Plane R2Using Stock Pieces of Materials with Fixed Length 认领 引用
3
作者 Jian-Ping Li Wen-Cheng Wang +1 位作者 Jun-Ran Lichen Yu-Jie Zheng 《Journal of the Operations Research Society of China》 EI CSCD 2024年第4期996-1021,共26页
In this paper,we address the problem of constructing a Steiner tree in the Euclidean plane R2using stock pieces of materials with fixed length,which is modelled as follows.Given a set X={r1,r2…,rn}of n te... In this paper,we address the problem of constructing a Steiner tree in the Euclidean plane R2using stock pieces of materials with fixed length,which is modelled as follows.Given a set X={r1,r2…,rn}of n terminals in R2and 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(n3)to resolve this new problem. 展开更多
关键词 Combinatorial optimization Euclidean plane Steiner tree Stock pieces of materials with fixed length Approximation algorithms
已选0条
引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 下一页 到第 页
在线咨询 使用帮助 返回顶部 意见反馈