Fog Computing is a new platform that can serve mobile devices in the local area. In Fog Computing, the resources need to be shared or cached in the widely deployed Fog clusters. In this paper, we propose a Steiner tre...Fog Computing is a new platform that can serve mobile devices in the local area. In Fog Computing, the resources need to be shared or cached in the widely deployed Fog clusters. In this paper, we propose a Steiner tree based caching scheme, in which the Fog servers, when caching resources, first produce a Steiner tree to minimize the total path weight(or cost) such that the cost of resource caching using this tree could be minimized. Then we give a running illustration to show how the Fog Computing works and we compare the traditional shortest path scheme with the proposed one. The outcome shows that the Steiner tree based scheme could work more efficiently.展开更多
Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a ...Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ（G） =Δ（T） and the number of leaves of T is not greater than n D（G）＋1,where D（G） is the diameter of G.展开更多
The rectilinear Steiner minimal tree （RSMT） problem is one of the fundamental problems in physical design, especially in routing, which is known to be NP-complete. This paper presents an algorithm, called ACO-Steine...The rectilinear Steiner minimal tree （RSMT） problem is one of the fundamental problems in physical design, especially in routing, which is known to be NP-complete. This paper presents an algorithm, called ACO-Steiner, for RSMT construction based on ant colony optimization （ACO）. An RSMT is constructed with ants＇ movements in Hanan grid, and then the constraint of Hanan grid is broken to accelerate ants＇ movements to improve the performance of the algorithm. This algorithm has been implemented on a Sun workstation with Unix operating system and the results have been compared with the fastest exact RSMT algorithm, GeoSteiner 3.1 and a recent heuristic using batched greedy triple construction （BGTC）. Experimental results show that ACO-Steiner can get a short running time and keep the high performance. Furthermore, it is Mso found that the ACO-Steiner can be easily extended to be used to some other problems, such as rectilinear Steiner minimal tree avoiding obstacles, and congestion reduction in global routing.展开更多
Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-t...Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-to-end deep neural networks for solving routing problems.However,such methods typically produce sequences of vertices,which make it difficult to apply them to general combinatorial optimization problems where the solution set consists of edges,as in various spanning tree problems.In this paper,we propose NeuroPrim,a novel framework for solving various spanning tree problems by defining a Markov decision process for general combinatorial optimization problems on graphs.Our approach reduces the action and state space using Prim's algorithm and trains the resulting model using REINFORCE.We apply our framework to three difficult problems on the Euclidean space:the degree-constrained minimum spanning tree problem,the minimum routing cost spanning tree problem and the Steiner tree problem in graphs.Experimental results on literature instances demonstrate that our model outperforms strong heuristics and achieves small optimality gaps of up to 250 vertices.Additionally,we find that our model has strong generalization ability with no significant degradation observed on problem instances as large as 1,000.Our results suggest that our framework can be effective for solving a wide range of combinatorial optimization problems beyond spanning tree problems.展开更多
This paper addresses false data injection, which is one of the most significant security challenges in smart grids. Having an accurately estimated state is of great importance for maintaining a stable running conditio...This paper addresses false data injection, which is one of the most significant security challenges in smart grids. Having an accurately estimated state is of great importance for maintaining a stable running condition of smart grids. To preserve the accuracy of the estimated state, bad data detection(BDD) mechanisms are utilized to remove erroneous measurements due to meter failures or outside attacks. In this paper we use a graph-theoretic formulation for false data injection attacks in smart grids and propose defense mechanisms to mitigate this type of attacks. To this end, we discuss characteristics of a typical smart grid graph such as planarity. Then we propose three different approaches to find optimal protected meters set: a fast and efficient heuristic algorithm that works well in practice, an approximation algorithm that provides guarantee for the quality of the protected set, and an exact algorithm that finds the optimal solution. Our extensive simulation results show that our algorithms outperform similar existing solutions in terms of different performance metrics.展开更多
A special case of the bottleneck Steiner tree problem in the Euclidean plane was considered in this paper. The problem has applications in the design of wireless communication networks, multifacility location, VLSI ro...A special case of the bottleneck Steiner tree problem in the Euclidean plane was considered in this paper. The problem has applications in the design of wireless communication networks, multifacility location, VLSI routing and network routing. For the special case which requires that there should be no edge connecting any two Steiner points in the optimal solution, a 3-restricted Steiner tree can be found indicating the existence of the performance ratio root2. In this paper, the special case of the problem is proved to be NP-hard and cannot be approximated within ratio root2. First a simple polynomial time approximation algorithm with performance ratio root3 is presented. Then based on this algorithm and the existence of the 3-restricted Steiner tree, a polynomial time approximation algorithm with performance ratio-root2 + epsilon is proposed, for any epsilon > 0.展开更多
This paper considers a new form of the Steiner tree problem that is more practical and reliable,which we call Reliable Steiner Tree(RST)problem.The authors give a detailed definition for this new problem and design bo...This paper considers a new form of the Steiner tree problem that is more practical and reliable,which we call Reliable Steiner Tree(RST)problem.The authors give a detailed definition for this new problem and design both an exact algorithm and an approximation algorithm for it.The definition is based on the reliability of full components instead of Steiner vertices.The task is thus to find the most reliable full components to make up an optimum reliable Steiner tree.The exact algorithm designed for this problem utilizes a dynamic programming frame.The approximation algorithm designed in this paper exploits a local search strategy that looks for the best full component according to a selection function at a time.展开更多
This study proposes a multiple attribute group decisionmaking(MAGDM)approach on the basis of the plant growth simulation algorithm(PGSA)and interval 2-tuple weighted average operators for uncertain linguistic weighted...This study proposes a multiple attribute group decisionmaking(MAGDM)approach on the basis of the plant growth simulation algorithm(PGSA)and interval 2-tuple weighted average operators for uncertain linguistic weighted aggregation(ULWA).We provide an example for illustration and verification and compare several aggregation operators to indicate the optimality of the assembly method.In addition,we present two comparisons to demonstrate the practicality and effectiveness of the proposed method.The method can be used not only to aggregate MAGDM problems but also to solve multi-granularity uncertain linguistic information.Its high reliability,easy programming,and high-speed calculation can improve the efficiency of ULWA characteristics.Finally,the proposed method has the exact characteristics for linguistic information processing and can effectively avoid information distortion and loss.展开更多
The Euclidean Steiner minimum tree problem is a classical NP-hard combinatorial optimization problem.Because of the intrinsic characteristic of the hard computability,this problem cannot be solved accurately by effici...The Euclidean Steiner minimum tree problem is a classical NP-hard combinatorial optimization problem.Because of the intrinsic characteristic of the hard computability,this problem cannot be solved accurately by efficient algorithms up to now.Due to the extensive applications in real world,it is quite important to find some heuristics for it.The stochastic diffusion search algorithm is a newly population-based algorithm whose operating mechanism is quite different from ordinary intelligent algorithms,so this algorithm has its own advantage in solving some optimization problems.This paper has carefully studied the stochastic diffusion search algorithm and designed a cellular automata stochastic diffusion search algorithm for the Euclidean Steiner minimum tree problem which has low time complexity.Practical results show that the proposed algorithm can find approving results in short time even for the large scale size,while exact algorithms need to cost several hours.展开更多
This study aims to discuss the possibility of becoming conscious of certain aspects of one’s own existence through creative activity.The discussion involves Piagetian constructivism and Steiner’s ideas about human d...This study aims to discuss the possibility of becoming conscious of certain aspects of one’s own existence through creative activity.The discussion involves Piagetian constructivism and Steiner’s ideas about human development and is justified by the contribution of creative activity to the development of autonomy,according to Piaget,and to the development of an ethical individuality,according to Steiner.The participation of adults in sessions of creative process,as well as the questions posed after this activity,asking for the relationships between what they created and their life,is evidence of practices favourable to increasing the grasping of consciousness of self and of the process of developing an ethical individuality.展开更多
基金supported by the National High-Tech R&D Program(863Program)No.2015AA01A705the National Natural Science Foundation of China under Grant No.61202079+1 种基金the China Postdoctoral Science Foundation under Grant No.2014T70031the Fundamental Research Funds for the Central Universities of China No.2015JBM111
文摘Fog Computing is a new platform that can serve mobile devices in the local area. In Fog Computing, the resources need to be shared or cached in the widely deployed Fog clusters. In this paper, we propose a Steiner tree based caching scheme, in which the Fog servers, when caching resources, first produce a Steiner tree to minimize the total path weight(or cost) such that the cost of resource caching using this tree could be minimized. Then we give a running illustration to show how the Fog Computing works and we compare the traditional shortest path scheme with the proposed one. The outcome shows that the Steiner tree based scheme could work more efficiently.
基金Supported by the National Natural Science Foundation of China (No.10771091)Project of Knowledge and Science Innovation Program of Northwest Normal University (Grant No.NWNU-KJCXGC-3-47)
文摘Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ（G） =Δ（T） and the number of leaves of T is not greater than n D（G）＋1,where D（G） is the diameter of G.
基金This work was partially supported by the National Natural Science Foundation of China （NSFC） under Grant No. 60373012, and the Specialized Research Fund for the Doctoral Program of Higher Education （SRFDP） of China under Grant No. 20050003099. Some preliminary results of this work were presented at IEEE International Conference on Communications, Circuits and Systems （ICCCAS）, Chengdu, China, 2004.
文摘The rectilinear Steiner minimal tree （RSMT） problem is one of the fundamental problems in physical design, especially in routing, which is known to be NP-complete. This paper presents an algorithm, called ACO-Steiner, for RSMT construction based on ant colony optimization （ACO）. An RSMT is constructed with ants＇ movements in Hanan grid, and then the constraint of Hanan grid is broken to accelerate ants＇ movements to improve the performance of the algorithm. This algorithm has been implemented on a Sun workstation with Unix operating system and the results have been compared with the fastest exact RSMT algorithm, GeoSteiner 3.1 and a recent heuristic using batched greedy triple construction （BGTC）. Experimental results show that ACO-Steiner can get a short running time and keep the high performance. Furthermore, it is Mso found that the ACO-Steiner can be easily extended to be used to some other problems, such as rectilinear Steiner minimal tree avoiding obstacles, and congestion reduction in global routing.
基金supported by National Key R&D Program of China(Grant No.2021YFA1000403)National Natural Science Foundation of China(Grant No.11991022)+1 种基金the Strategic Priority Research Program of Chinese Academy of Sciences(Grant No.XDA27000000)the Fundamental Research Funds for the Central Universities。
文摘Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-to-end deep neural networks for solving routing problems.However,such methods typically produce sequences of vertices,which make it difficult to apply them to general combinatorial optimization problems where the solution set consists of edges,as in various spanning tree problems.In this paper,we propose NeuroPrim,a novel framework for solving various spanning tree problems by defining a Markov decision process for general combinatorial optimization problems on graphs.Our approach reduces the action and state space using Prim's algorithm and trains the resulting model using REINFORCE.We apply our framework to three difficult problems on the Euclidean space:the degree-constrained minimum spanning tree problem,the minimum routing cost spanning tree problem and the Steiner tree problem in graphs.Experimental results on literature instances demonstrate that our model outperforms strong heuristics and achieves small optimality gaps of up to 250 vertices.Additionally,we find that our model has strong generalization ability with no significant degradation observed on problem instances as large as 1,000.Our results suggest that our framework can be effective for solving a wide range of combinatorial optimization problems beyond spanning tree problems.
文摘This paper addresses false data injection, which is one of the most significant security challenges in smart grids. Having an accurately estimated state is of great importance for maintaining a stable running condition of smart grids. To preserve the accuracy of the estimated state, bad data detection(BDD) mechanisms are utilized to remove erroneous measurements due to meter failures or outside attacks. In this paper we use a graph-theoretic formulation for false data injection attacks in smart grids and propose defense mechanisms to mitigate this type of attacks. To this end, we discuss characteristics of a typical smart grid graph such as planarity. Then we propose three different approaches to find optimal protected meters set: a fast and efficient heuristic algorithm that works well in practice, an approximation algorithm that provides guarantee for the quality of the protected set, and an exact algorithm that finds the optimal solution. Our extensive simulation results show that our algorithms outperform similar existing solutions in terms of different performance metrics.
文摘A special case of the bottleneck Steiner tree problem in the Euclidean plane was considered in this paper. The problem has applications in the design of wireless communication networks, multifacility location, VLSI routing and network routing. For the special case which requires that there should be no edge connecting any two Steiner points in the optimal solution, a 3-restricted Steiner tree can be found indicating the existence of the performance ratio root2. In this paper, the special case of the problem is proved to be NP-hard and cannot be approximated within ratio root2. First a simple polynomial time approximation algorithm with performance ratio root3 is presented. Then based on this algorithm and the existence of the 3-restricted Steiner tree, a polynomial time approximation algorithm with performance ratio-root2 + epsilon is proposed, for any epsilon > 0.
基金supported by National Natural Science Foundation of China under Grant Nos.71171189,71271204,11101420Knowledge Innovation Program of the Chinese Academy of Sciences under Grant No.KGCX2-RW-329
文摘This paper considers a new form of the Steiner tree problem that is more practical and reliable,which we call Reliable Steiner Tree(RST)problem.The authors give a detailed definition for this new problem and design both an exact algorithm and an approximation algorithm for it.The definition is based on the reliability of full components instead of Steiner vertices.The task is thus to find the most reliable full components to make up an optimum reliable Steiner tree.The exact algorithm designed for this problem utilizes a dynamic programming frame.The approximation algorithm designed in this paper exploits a local search strategy that looks for the best full component according to a selection function at a time.
基金supported by the National Natural Science Foundation of China(71771118 71471083)+1 种基金the Ministry of Education Humanities and Social Sciences Foundation of China(18YJCZH146)the Nanjing University Double First-Class project
文摘This study proposes a multiple attribute group decisionmaking(MAGDM)approach on the basis of the plant growth simulation algorithm(PGSA)and interval 2-tuple weighted average operators for uncertain linguistic weighted aggregation(ULWA).We provide an example for illustration and verification and compare several aggregation operators to indicate the optimality of the assembly method.In addition,we present two comparisons to demonstrate the practicality and effectiveness of the proposed method.The method can be used not only to aggregate MAGDM problems but also to solve multi-granularity uncertain linguistic information.Its high reliability,easy programming,and high-speed calculation can improve the efficiency of ULWA characteristics.Finally,the proposed method has the exact characteristics for linguistic information processing and can effectively avoid information distortion and loss.
基金the National Natural Science Foundation of China (No.70871081)the Science and Technology Department Research Project of Henan Province(No.112102310448)the Natural Science Foundation of Henan University (No.2010YBZR047)
文摘The Euclidean Steiner minimum tree problem is a classical NP-hard combinatorial optimization problem.Because of the intrinsic characteristic of the hard computability,this problem cannot be solved accurately by efficient algorithms up to now.Due to the extensive applications in real world,it is quite important to find some heuristics for it.The stochastic diffusion search algorithm is a newly population-based algorithm whose operating mechanism is quite different from ordinary intelligent algorithms,so this algorithm has its own advantage in solving some optimization problems.This paper has carefully studied the stochastic diffusion search algorithm and designed a cellular automata stochastic diffusion search algorithm for the Euclidean Steiner minimum tree problem which has low time complexity.Practical results show that the proposed algorithm can find approving results in short time even for the large scale size,while exact algorithms need to cost several hours.
文摘This study aims to discuss the possibility of becoming conscious of certain aspects of one’s own existence through creative activity.The discussion involves Piagetian constructivism and Steiner’s ideas about human development and is justified by the contribution of creative activity to the development of autonomy,according to Piaget,and to the development of an ethical individuality,according to Steiner.The participation of adults in sessions of creative process,as well as the questions posed after this activity,asking for the relationships between what they created and their life,is evidence of practices favourable to increasing the grasping of consciousness of self and of the process of developing an ethical individuality.
