Gravity-based heuristic for set covering problems and its application in fault diagnosis

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.

Continuity of Solution Mappings for Parametric Set Optimization Problems under Partial Order Relations

This paper mainly investigates the semicontinuity of solution mappings for set optimization problems under a partial order set relation instead of upper and lower set less order relations. To this end, we propose two types of monotonicity definition for the set-valued mapping introduced by two nonlinear scalarization functions which are presented by these partial order relations. Then, we give some sufficient conditions for the semicontinuity and closedness of solution mappings for parametric set optimization problems. The results presented in this paper are new and extend the main results given by some authors in the literature.

ENERGY-EFFICIENT HEURISTIC METRIC FOR SCP IN SENSOR NETWORKS

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.

Binary Fruit Fly Swarm Algorithms for the Set Covering Problem

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.

Ontology-Based Semantic Annotation for Problem Set Archives in the Web

Aimming at the difficulty in getting semantic informarton from each problem in problem set archives, We propose a new method of ontology based semantic annotation for problem set archives, which utilizes programming knowledge domain ontology to add semantic annotations to problems in the Web. The system we developed adds semantic annotation for each problem in the form of Extensible Makeup Language. Our method overcomes the difficulty of extracting semantics from problem set archives and the efficiency of this method is demonstrated through a case study. Having semantic annotations of problems, a student can efficiently locate the problems that logically corre spond to his knowledge.

Existence of solutions for fourth-order boundary value problem with parameter

This paper is a sequel to a previous paper （Yang, Y. and Zhang, J. H. Existence of solutions for some fourth-order boundary value problems with parameters. Nonlinear Anal. 69（2）, 1364-1375 （2008）） in which the nontrivial solutions to the fourthorder boundary value problems were studied. In the current work with the same conditions near infinity but different near zero, the positive, negative, and sign-changing solutions are obtained by the critical point theory, retracting property, and invariant sets.

Maximum-Profit Advertising Strategy Using Crowdsensing Trajectory Data

Out-door billboard advertising plays an important role in attracting potential customers.However,whether a customer can be attracted is influenced by many factors,such as the probability that he/she sees the billboard,the degree of his/her interest,and the detour distance for buying the product.Taking the above factors into account,we propose advertising strategies for selecting an effective set of billboards under the advertising budget to maximize commercial profit.By using the data collected by Mobile Crowdsensing(MCS),we extract potential customers’implicit information,such as their trajectories and preferences.We then study the billboard selection problem under two situations,where the advertiser may have only one or multiple products.When only one kind of product needs advertising,the billboard selection problem is formulated as the probabilistic set coverage problem.We propose two heuristic advertising strategies to greedily select advertising billboards,which achieves the expected maximum commercial profit with the lowest cost.When the advertiser has multiple products,we formulate the problem as searching for an optimal solution and adopt the simulated annealing algorithm to search for global optimum instead of local optimum.Extensive experiments based on three real-world data sets verify that our proposed advertising strategies can achieve the superior commercial profit compared with the state-of-the-art strategies.

SET COVERING-BASED TOPSIS METHOD FOR SLOVING SUP-T EQUATION CONSTRAINED MULTI-OBJECTIVE OPTIMIZATION PROBLEMS

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.

On the Stability of the Solution Set Mappings to Parametric Set Optimization Problems

In this paper,under some suitable assumptions without any involving information on the solution set,we give some sufficient conditions for the upper semicontinuity,lower semicontinuity,and closedness of the solution set mapping to a parametric set optimization problem with possible less order relation.

On Some Proximity Problems of Colored Sets

The maximum diameter color-spanning set problem（MaxDCS） is defined as follows： given n points with m colors, select m points with m distinct colors such that the diameter of the set of chosen points is maximized. In this paper, we design an optimal O（n log n） time algorithm using rotating calipers for MaxDCS in the plane. Our algorithm can also be used to solve the maximum diameter problem of imprecise points modeled as polygons. We also give an optimal algorithm for the all farthest foreign neighbor problem（AFFN） in the plane, and propose algorithms to answer the farthest foreign neighbor query（FFNQ） of colored sets in two- and three-dimensional space. Furthermore, we study the problem of computing the closest pair of color-spanning set（CPCS） in d-dimensional space, and remove the log m factor in the best known time bound if d is a constant.

Restricted parameter range promise set cover problems are easy

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.

Maximum Independent Sets and Supervised Learning

The paper discusses an enhancement to a recently presented supervised learning algorithm to solve the Maximum Independent Set problem.In particular,it is shown that the algorithm can be improved by simplifying the task learnt by the neural network adopted,with measurable effects on the quality of the solutions provided on unseen instances.Empirical results are presented to validate the idea..

An Approximation Algorithm for P-prize-collecting Set Cover Problem

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.

Comparing two sets without disclosing them

Secure multiparty computation has become a central research focus in the international cryptographic community. Secure comparing two sets is an important problem in secure multiparty computation. The research on privately determining whether two sets are equal has not been investigated. This study solves the problem by mapping these sets into natural numbers and then comparing correspond- ing numbers, We propose two secure multiparty computation protocols for comparing two sets. It is proved by well-accepted simulation paradigm that these solutions are private in semi-honest model. These solutions have important significance in constructing other secure multiparty computation protocols.

A Binary Particle Swarm Optimization for the Minimum Weight Dominating Set Problem

The minimum weight dominating set problem （MWDSP） is an NP-hard problem with a lot of real-world applications. Several heuristic algorithms have been presented to produce good quality solutions. However, the solution time of them grows very quickly as the size of the instance increases. In this paper, we propose a binary particle swarm optimization （FBPSO） for solving the MWDSP approximately. Based on the characteristic of MWDSP, this approach designs a new position updating rule to guide the search to a promising area. An iterated greedy tabu search is used to enhance the solution quality quickly. In addition, several stochastic strategies are employed to diversify the search and prevent premature convergence. These methods maintain a good balance between the exploration and the exploitation. Experimental studies on 106 groups of 1 060 instances show that FBPSO is able to identify near optimal solutions in a short running time. The average deviation between the solutions obtained by FBPSO and the best known solutions is 0.441%. Moreover, the average solution time of FBPSO is much less than that of other existing algorithms. In particular, with the increasing of instance size, the solution time of FBPSO grows much more slowly than that of other existing algorithms.

A uniform solution to the independent set problem through tissue P systems with cell separation

Membrane computing is an emergent branch of natural computing, which is inspired by the structure and the functioning of living cells, as well as the organization of cells in tissues, organs, and other higher order structures. Tissue P systems are a class of the most investigated computing mod- els in the framework of membrane computing, especially in the aspect of efficiency. To generate an exponential resource in a polynomial time, cell separation is incorporated into such systems, thus obtaining so called tissue P systems with cell separation. In this work, we exploit the computational efficiency of this model and construct a uniform family of such tissue P systems for solving the independent set problem, a well-known NP-complete problem, by which an efficient so- lution can be obtained in polynomial time.

Input Data Dependency of a Genetic Algorithm to Solve the Set Covering Problem

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.