A novel algorithm named randomized binary gravita- tional search （RBGS） algorithm is proposed for the set covering problem （SCP）. It differs from previous SCP approaches because it does not work directly on the SC...A novel algorithm named randomized binary gravita- tional search （RBGS） algorithm is proposed for the set covering problem （SCP）. It differs from previous SCP approaches because it does not work directly on the SCP matrix. In the proposed algo- rithm, the solution of SCP is viewed as multi-dimension position of objects in the binary search space. All objects in the space attract each other by the gravity force, and this force causes a global movement of all objects towards the objects with heavier masses which correspond to good solutions. Computation results show that the proposed algorithm is very competitive. In addition, the proposed aigodthm is extended for SCP to solve the fault diagno- sis problem in graph-based systems.展开更多
Currently,the industry is experiencing an exponential increase in dealing with binary-based combinatorial problems.In this sense,metaheuristics have been a common trend in the field in order to design approaches to so...Currently,the industry is experiencing an exponential increase in dealing with binary-based combinatorial problems.In this sense,metaheuristics have been a common trend in the field in order to design approaches to solve them successfully.Thus,a well-known strategy consists in the use of algorithms based on discrete swarms transformed to perform in binary environments.Following the No Free Lunch theorem,we are interested in testing the performance of the Fruit Fly Algorithm,this is a bio-inspired metaheuristic for deducing global optimization in continuous spaces,based on the foraging behavior of the fruit fly,which usually has much better sensory perception of smell and vision than any other species.On the other hand,the Set Coverage Problem is a well-known NP-hard problem with many practical applications,including production line balancing,utility installation,and crew scheduling in railroad and mass transit companies.In this paper,we propose different binarization methods for the Fruit Fly Algorithm,using Sshaped and V-shaped transfer functions and various discretization methods to make the algorithm work in a binary search space.We are motivated with this approach,because in this way we can deliver to future researchers interested in this area,a way to be able to work with continuous metaheuristics in binary domains.This new approach was tested on benchmark instances of the Set Coverage Problem and the computational results show that the proposed algorithm is robust enough to produce good results with low computational cost.展开更多
A genetic algorithm to solve the set covering problem proposed in the literature had some improvements which gave better solutions, i.e., better chromosomes in the first starting population, taking full account of do...A genetic algorithm to solve the set covering problem proposed in the literature had some improvements which gave better solutions, i.e., better chromosomes in the first starting population, taking full account of domain specific knowledge with sound programming skill. We have further investigated the input data dependency of their genetic algorithm, i.e., the dependency on costs and density. We have found that for input problem data sets with densities greater than or equal to 3%, our genetic algorithm is still practical both in computing time and approximation ratio.展开更多
Secure group communications are restrained by the number of the group size,number of changes and their distribution,all existing works do not meet the commands of applications with large group size and high dynamic me...Secure group communications are restrained by the number of the group size,number of changes and their distribution,all existing works do not meet the commands of applications with large group size and high dynamic members.In this paper,minimum exact cover problem for group key distribution(GMECP)is presented,and a heuristic solution is testified.Then an algorithm of batch rekeying with renewing cost tending to zero is illustrated,which can process any large number of change requests with best security guaranteed.Efficiency analysis and simulation test show that the achievement can improve the efficiency of any tree-based group key management.展开更多
A perturbation method is applied to study the structure of the ground state of the adiabatic quantum optimization for the exact cover 3 problem. It is found that the instantaneous ground state near the end of the evol...A perturbation method is applied to study the structure of the ground state of the adiabatic quantum optimization for the exact cover 3 problem. It is found that the instantaneous ground state near the end of the evolution is mainly composed of the eigenstates of the problem Hamiltonian, which are Hamming close to the solution state. And the instantaneous ground state immediately after the starting is mainly formed of low energy eigenstates of the problem Hamiltonian. These results are then applied to estimate the minimum gap for a special case.展开更多
A heuristic metric is presented to achieve the optimal connected set covering problem （SCP） in sensor networks. The coverage solution with the energy efficiency can guarantee that all targets are fully covered. Amon...A heuristic metric is presented to achieve the optimal connected set covering problem （SCP） in sensor networks. The coverage solution with the energy efficiency can guarantee that all targets are fully covered. Among targets, the crucial ones are redundantly covered to ensure more reliable monitors. And the information collected by the above coverage solution can be transmitted to Sink by the connected data-gathering structure. A novel ant colony optimization （ACO） algorithm--improved-MMAS-ACS-hybrid algorithm （IMAH） is adopted to achieve the above metric. Based on the design of the heuristic factor, artificial ants can adaptively detect the coverage and energy status of sensor networks and find the low-energy-cost paths to keep the communication connectivity to Sink. By introducing the pheromone-judgment-factor and the evaluation function to the pheromone updating rule, the pheromone trail on the global-best solution is enhanced, while avoiding the premature stagnation. Finally, the energy efficiency set can be obtained with high coverage-efficiency to all targets and reliable connectivity to Sink and the lifetime of the connected coverage set is prolonged.展开更多
This paper considers solving a multi-objective optimization problem with sup-T equation constraints A set covering-based technique for order of preference by similarity to the ideal solution is proposed for solving su...This paper considers solving a multi-objective optimization problem with sup-T equation constraints A set covering-based technique for order of preference by similarity to the ideal solution is proposed for solving such a problem. It is shown that a compromise solution of the sup-T equation constrained multi-objective optimization problem can be obtained by ＂solving an associated set covering problem. A surrogate heuristic is then applied to solve the resulting optimization problem. Numerical experiments on solving randomly generated multi-objective optimization problems with sup-T equation constraints are included. Our computational results confirm the efficiency of the proposed method and show its potential for solving large scale sup-T equation constrained multi-objective optimization problems.展开更多
The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with...The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.展开更多
This paper describes an extremely fast polynomial time algorithm, the NOVCA （Near Optimal Vertex Cover Algorithm） that produces an optimal or near optimal vertex cover for any known undirected graph G （V, E）. NOVC...This paper describes an extremely fast polynomial time algorithm, the NOVCA （Near Optimal Vertex Cover Algorithm） that produces an optimal or near optimal vertex cover for any known undirected graph G （V, E）. NOVCA is based on the idea of（l） including the vertex having maximum degree in the vertex cover and （2） rendering the degree of a vertex to zero by including all its adjacent vertices. The three versions of algorithm, NOVCA-I, NOVCA-II, and NOVCA-random, have been developed. The results identifying bounds on the size of the minimum vertex cover as well as polynomial complexity of algorithm are given with experimental verification. Future research efforts will be directed at tuning the algorithm and providing proof for better approximation ratio with NOVCA compared to any available vertex cover algorithms.展开更多
In this paper,we consider the P-prize-collecting set cover(P-PCSC)problem,which is a generalization of the set cover problem.In this problem,we are given a set system(U,S),where U is a ground set and S⊆2U is a collect...In this paper,we consider the P-prize-collecting set cover(P-PCSC)problem,which is a generalization of the set cover problem.In this problem,we are given a set system(U,S),where U is a ground set and S⊆2U is a collection of subsets satisfying∪S∈SS=U.Every subset in S has a nonnegative cost,and every element in U has a nonnegative penalty cost and a nonnegative profit.Our goal is to find a subcollection C⊆S such that the total cost,consisting of the cost of subsets in C and the penalty cost of the elements not covered by C,is minimized and at the same time the combined profit of the elements covered by C is at least P,a specified profit bound.Our main work is to obtain a 2f+ε-approximation algorithm for the P-PCSC problem by using the primal-dual and Lagrangian relaxation methods,where f is the maximum frequency of an element in the given set system(U,S)andεis a fixed positive number.展开更多
The restricted parameter range set cover problem is a weak form of the NP-hard set cover problem with the restricted range of parameters. We give a polynomial time algorithm for this problem by lattices.
We introduce splitting coverings to enhance the well known analogy between field extensions and covering spaces. Semi-topological Galois groups are defined for Weier- strass polynomials and a Galois correspondence is ...We introduce splitting coverings to enhance the well known analogy between field extensions and covering spaces. Semi-topological Galois groups are defined for Weier- strass polynomials and a Galois correspondence is proved. Combining results from braid groups, we solve the topological inverse Galois problem. As an application, symmetric and cyclic groups are realized over Q.展开更多
基金supported by the National Natural Science Foundation of China (4100605850909096)
文摘A novel algorithm named randomized binary gravita- tional search （RBGS） algorithm is proposed for the set covering problem （SCP）. It differs from previous SCP approaches because it does not work directly on the SCP matrix. In the proposed algo- rithm, the solution of SCP is viewed as multi-dimension position of objects in the binary search space. All objects in the space attract each other by the gravity force, and this force causes a global movement of all objects towards the objects with heavier masses which correspond to good solutions. Computation results show that the proposed algorithm is very competitive. In addition, the proposed aigodthm is extended for SCP to solve the fault diagno- sis problem in graph-based systems.
文摘Currently,the industry is experiencing an exponential increase in dealing with binary-based combinatorial problems.In this sense,metaheuristics have been a common trend in the field in order to design approaches to solve them successfully.Thus,a well-known strategy consists in the use of algorithms based on discrete swarms transformed to perform in binary environments.Following the No Free Lunch theorem,we are interested in testing the performance of the Fruit Fly Algorithm,this is a bio-inspired metaheuristic for deducing global optimization in continuous spaces,based on the foraging behavior of the fruit fly,which usually has much better sensory perception of smell and vision than any other species.On the other hand,the Set Coverage Problem is a well-known NP-hard problem with many practical applications,including production line balancing,utility installation,and crew scheduling in railroad and mass transit companies.In this paper,we propose different binarization methods for the Fruit Fly Algorithm,using Sshaped and V-shaped transfer functions and various discretization methods to make the algorithm work in a binary search space.We are motivated with this approach,because in this way we can deliver to future researchers interested in this area,a way to be able to work with continuous metaheuristics in binary domains.This new approach was tested on benchmark instances of the Set Coverage Problem and the computational results show that the proposed algorithm is robust enough to produce good results with low computational cost.
文摘A genetic algorithm to solve the set covering problem proposed in the literature had some improvements which gave better solutions, i.e., better chromosomes in the first starting population, taking full account of domain specific knowledge with sound programming skill. We have further investigated the input data dependency of their genetic algorithm, i.e., the dependency on costs and density. We have found that for input problem data sets with densities greater than or equal to 3%, our genetic algorithm is still practical both in computing time and approximation ratio.
基金Supported by the National Natural Science Foundation of China(60572049)
文摘Secure group communications are restrained by the number of the group size,number of changes and their distribution,all existing works do not meet the commands of applications with large group size and high dynamic members.In this paper,minimum exact cover problem for group key distribution(GMECP)is presented,and a heuristic solution is testified.Then an algorithm of batch rekeying with renewing cost tending to zero is illustrated,which can process any large number of change requests with best security guaranteed.Efficiency analysis and simulation test show that the achievement can improve the efficiency of any tree-based group key management.
基金Project supported by the National Natural Science Foundation of China(Grant No.61173050)
文摘A perturbation method is applied to study the structure of the ground state of the adiabatic quantum optimization for the exact cover 3 problem. It is found that the instantaneous ground state near the end of the evolution is mainly composed of the eigenstates of the problem Hamiltonian, which are Hamming close to the solution state. And the instantaneous ground state immediately after the starting is mainly formed of low energy eigenstates of the problem Hamiltonian. These results are then applied to estimate the minimum gap for a special case.
文摘A heuristic metric is presented to achieve the optimal connected set covering problem （SCP） in sensor networks. The coverage solution with the energy efficiency can guarantee that all targets are fully covered. Among targets, the crucial ones are redundantly covered to ensure more reliable monitors. And the information collected by the above coverage solution can be transmitted to Sink by the connected data-gathering structure. A novel ant colony optimization （ACO） algorithm--improved-MMAS-ACS-hybrid algorithm （IMAH） is adopted to achieve the above metric. Based on the design of the heuristic factor, artificial ants can adaptively detect the coverage and energy status of sensor networks and find the low-energy-cost paths to keep the communication connectivity to Sink. By introducing the pheromone-judgment-factor and the evaluation function to the pheromone updating rule, the pheromone trail on the global-best solution is enhanced, while avoiding the premature stagnation. Finally, the energy efficiency set can be obtained with high coverage-efficiency to all targets and reliable connectivity to Sink and the lifetime of the connected coverage set is prolonged.
文摘This paper considers solving a multi-objective optimization problem with sup-T equation constraints A set covering-based technique for order of preference by similarity to the ideal solution is proposed for solving such a problem. It is shown that a compromise solution of the sup-T equation constrained multi-objective optimization problem can be obtained by ＂solving an associated set covering problem. A surrogate heuristic is then applied to solve the resulting optimization problem. Numerical experiments on solving randomly generated multi-objective optimization problems with sup-T equation constraints are included. Our computational results confirm the efficiency of the proposed method and show its potential for solving large scale sup-T equation constrained multi-objective optimization problems.
文摘The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.
文摘This paper describes an extremely fast polynomial time algorithm, the NOVCA （Near Optimal Vertex Cover Algorithm） that produces an optimal or near optimal vertex cover for any known undirected graph G （V, E）. NOVCA is based on the idea of（l） including the vertex having maximum degree in the vertex cover and （2） rendering the degree of a vertex to zero by including all its adjacent vertices. The three versions of algorithm, NOVCA-I, NOVCA-II, and NOVCA-random, have been developed. The results identifying bounds on the size of the minimum vertex cover as well as polynomial complexity of algorithm are given with experimental verification. Future research efforts will be directed at tuning the algorithm and providing proof for better approximation ratio with NOVCA compared to any available vertex cover algorithms.
基金This work was supported by the National Natural Science Foundation of China(No.11971146)the Natural Science Foundation of Hebei Province of China(Nos.A2019205089 and A2019205092)+1 种基金Hebei Province Foundation for Returnees(No.CL201714)Overseas Expertise Introduction Program of Hebei Auspices(No.25305008).
文摘In this paper,we consider the P-prize-collecting set cover(P-PCSC)problem,which is a generalization of the set cover problem.In this problem,we are given a set system(U,S),where U is a ground set and S⊆2U is a collection of subsets satisfying∪S∈SS=U.Every subset in S has a nonnegative cost,and every element in U has a nonnegative penalty cost and a nonnegative profit.Our goal is to find a subcollection C⊆S such that the total cost,consisting of the cost of subsets in C and the penalty cost of the elements not covered by C,is minimized and at the same time the combined profit of the elements covered by C is at least P,a specified profit bound.Our main work is to obtain a 2f+ε-approximation algorithm for the P-PCSC problem by using the primal-dual and Lagrangian relaxation methods,where f is the maximum frequency of an element in the given set system(U,S)andεis a fixed positive number.
基金Acknowledgements This work was supported by the National Natural Science Foundation of China （Grant No. 11371138）.
文摘The restricted parameter range set cover problem is a weak form of the NP-hard set cover problem with the restricted range of parameters. We give a polynomial time algorithm for this problem by lattices.
文摘We introduce splitting coverings to enhance the well known analogy between field extensions and covering spaces. Semi-topological Galois groups are defined for Weier- strass polynomials and a Galois correspondence is proved. Combining results from braid groups, we solve the topological inverse Galois problem. As an application, symmetric and cyclic groups are realized over Q.
