Network virtualization is known as a promising technology to tackle the ossification of current Internet and will play an important role in the future network area. Virtual network embedding(VNE) is a key issue in net...Network virtualization is known as a promising technology to tackle the ossification of current Internet and will play an important role in the future network area. Virtual network embedding(VNE) is a key issue in network virtualization. VNE is NP-hard and former VNE algorithms are mostly heuristic in the literature.VNE exact algorithms have been developed in recent years. However, the constraints of exact VNE are only node capacity and link bandwidth.Based on these, this paper presents an exact VNE algorithm, ILP-LC, which is based on Integer Linear Programming(ILP), for embedding virtual network request with location constraints. This novel algorithm is aiming at mapping virtual network request(VNR) successfully as many as possible and consuming less substrate resources.The topology of each VNR is randomly generated by Waxman model. Simulation results show that the proposed ILP-LC algorithm outperforms the typical heuristic algorithms in terms of the VNR acceptance ratio, at least 15%.展开更多
Capacitated facility location problem(CFLP)is a classical combinatorial optimization problem that has various applications in operations research,theoretical computer science,and management science.In the CFLP,we have...Capacitated facility location problem(CFLP)is a classical combinatorial optimization problem that has various applications in operations research,theoretical computer science,and management science.In the CFLP,we have a potential facilities set and a clients set.Each facility has a certain capacity and an open cost,and each client has a spliitable demand that need to be met.The goal is to open some facilities and assign all clients to these open facilities so that the total cost is as low as possible.The CFLP is NP-hard(non-deterministic polynomial-hard),and a large amount of work has been devoted to designing approximation algorithms for CFLP and its variants.Following this vein,we introduce a new variant of CFLP called capacitated uniform facility location problem with soft penalties(CUFLPSP),in which the demand of each client can be partially rejected by paying penalty costs.As a result,we present a linear programming-rounding(LP-rounding)based 5.5122-approximation algorithm for the CUFLPSP.展开更多
为解决点刻式直接零件标志(Direct part mark,DPM)码基本单元分割困难、区域定位欠精确等问题,提出使用超像素分割和谱聚类相结合的算法,对含有DPM区域的图像进行初步分割和精确定位.首先为提高超像素分割的准确、快速和完整性,本文利...为解决点刻式直接零件标志(Direct part mark,DPM)码基本单元分割困难、区域定位欠精确等问题,提出使用超像素分割和谱聚类相结合的算法,对含有DPM区域的图像进行初步分割和精确定位.首先为提高超像素分割的准确、快速和完整性,本文利用近邻传播聚类思想实现自动聚类得到超像素区域,并引入边缘置信度调整超像素边缘,形成自适应边缘简单线性迭代聚类(Adaptive edge simple linear iterative clustering,AE-SLIC)算法.该算法改进了简单线性迭代聚类(Simple linear iterative clustering,SLIC)超像素分割算法存在的未明确界定超像素区域边缘信息和分割数目无法自适应确定等问题;其次,将超像素作为谱聚类中图的顶点进行二次聚类,DPM区域内超像素因相似度高而被聚集为一类,从而完成点刻式DPM区域的精确定位.经实验测试和分析,本文算法得到的超像素分割结果在完整性、运算复杂度等方面优于常见的超像素分割算法.与基于像素点运算的传统定位算法相比,本文算法具有良好的实时性、定位准确率和鲁棒性.展开更多
基金supported by the National Basic Research Program of China(973 Program)under Grant 2013CB329005
文摘Network virtualization is known as a promising technology to tackle the ossification of current Internet and will play an important role in the future network area. Virtual network embedding(VNE) is a key issue in network virtualization. VNE is NP-hard and former VNE algorithms are mostly heuristic in the literature.VNE exact algorithms have been developed in recent years. However, the constraints of exact VNE are only node capacity and link bandwidth.Based on these, this paper presents an exact VNE algorithm, ILP-LC, which is based on Integer Linear Programming(ILP), for embedding virtual network request with location constraints. This novel algorithm is aiming at mapping virtual network request(VNR) successfully as many as possible and consuming less substrate resources.The topology of each VNR is randomly generated by Waxman model. Simulation results show that the proposed ILP-LC algorithm outperforms the typical heuristic algorithms in terms of the VNR acceptance ratio, at least 15%.
基金supported by the National Natural Science Foundation of China(Nos.11971349,12071442,12371320,and 12371318).
文摘Capacitated facility location problem(CFLP)is a classical combinatorial optimization problem that has various applications in operations research,theoretical computer science,and management science.In the CFLP,we have a potential facilities set and a clients set.Each facility has a certain capacity and an open cost,and each client has a spliitable demand that need to be met.The goal is to open some facilities and assign all clients to these open facilities so that the total cost is as low as possible.The CFLP is NP-hard(non-deterministic polynomial-hard),and a large amount of work has been devoted to designing approximation algorithms for CFLP and its variants.Following this vein,we introduce a new variant of CFLP called capacitated uniform facility location problem with soft penalties(CUFLPSP),in which the demand of each client can be partially rejected by paying penalty costs.As a result,we present a linear programming-rounding(LP-rounding)based 5.5122-approximation algorithm for the CUFLPSP.
文摘为解决点刻式直接零件标志(Direct part mark,DPM)码基本单元分割困难、区域定位欠精确等问题,提出使用超像素分割和谱聚类相结合的算法,对含有DPM区域的图像进行初步分割和精确定位.首先为提高超像素分割的准确、快速和完整性,本文利用近邻传播聚类思想实现自动聚类得到超像素区域,并引入边缘置信度调整超像素边缘,形成自适应边缘简单线性迭代聚类(Adaptive edge simple linear iterative clustering,AE-SLIC)算法.该算法改进了简单线性迭代聚类(Simple linear iterative clustering,SLIC)超像素分割算法存在的未明确界定超像素区域边缘信息和分割数目无法自适应确定等问题;其次,将超像素作为谱聚类中图的顶点进行二次聚类,DPM区域内超像素因相似度高而被聚集为一类,从而完成点刻式DPM区域的精确定位.经实验测试和分析,本文算法得到的超像素分割结果在完整性、运算复杂度等方面优于常见的超像素分割算法.与基于像素点运算的传统定位算法相比,本文算法具有良好的实时性、定位准确率和鲁棒性.
