32897108
A New Hybrid Genetic Algorithm for the Robust Graph Coloring Problem
The RGCP (Robust Graph Coloring problem) is a new variant of the traditional graph coloring problem. It has numerous practical applications in real world like timetabling and crew scheduling. The traditional graph coloring problem focuses on minimizing the number of colors used in the graph. RGCP focuses on the robustness of the coloring so that the coloring is able to handle uncertainty that often occurs in the real world. By that, we mean that given a fixed number of colors we would like to color the graph so that adjacent vertices are assigned different colors with the consideration of the possible appearance of the missing edges. In this paper, we present a new hybrid genetic algorithm (GA), which embeds two kinds of local search algorithms – enumerative search and random search within the GA framework. In addition, we integrate a partition based encoding scheme with a specialized crossover operator into our GA method. We also propose an adaptive scheme that alternates between two local search methods to increase performance. Experimental results show that our new algorithm outperforms the best published results in terms of the quality of solutions and the computing time needed.
32718924
k-Center Problems with Minimum Coverage
The k-center problem is a well-known facility location problem and can be described as follows: Given a complete undirected graph G=(V,E), a metric d:V×V→ℝ + and a positive integer k, we seek a subset U ⊆ V of at most k centers which minimizes the maximum distances from points in V to U. Formally, the objective function is given by: 
 
$$ \textstyle\min_{U\subseteq V,|U|\leq k}\max_{v\in V}\min_{r\in U}d(v,r).$$ 
 
As a typical example, we may want to set up k service centers (e.g., police stations, fire stations, hospitals, polling centers) and minimize the maximum distances between each client and these centers. The problem is known to be \(\mathcal{NP}\)-hard [2].
15711911
A stochastic beam search for the berth allocation problem
In this paper, the optimization of the Berth Allocation Problem (BAP) is transformed into a multiple stage decision making procedure and a new multiple stage search method, namely stochastic beam search algorithm, is proposed to solve it. New techniques such as an improved beam search scheme, a two-phase node goodness estimation, and a stochastic node selection criteria are proposed. Real-life information provided by Singapore Port was collected as our test data. Experimental results show that the proposed stochastic beam search is more accurate and efficient than both the state-of-the-art meta-heuristic and the traditional determinist beam search.
39897206
A Compromised Large-Scale Neighborhood Search Heuristic for Cargo Loading Planning
In this work, we propose a compromised large-scale neighborhood, which is embedded in simulated annealing to solve a cargo loading planning problem arising in logistics industry. It is "compromised" because it makes a tradeoff between the extensive backward checking work incurred in traditional subset-disjoint restriction and the possible infeasibility resulting from the relaxing the restriction. Extensive experiments have shown the competitive advantages of the heuristic approach. The proposed neighborhood search method is generally applicable.
44734123
Meta-heuristic Algorithm for the Transshipment Problem with Fixed Transportation Schedules
In this work, we develop an efficient meta-heuristic genetic algorithm for a different type of transshipment problem with supplier and customer time windows, where flow through the crossdock (a kind of transshipment center) is constrained by fixed transportation schedules and crossdocks capacities, and which was proved to be NP -complete in the strong sense. And computational experiments are conducted to show the proposed heuristic outperforms CPLEX.
23454249
A compromised large-scale neighborhood search heuristic for capacitated air cargo loading planning
Cost effectiveness is central to the air freight forwarders. In this work, we study how an air freight forwarder should plan its cargo loading in order to minimize the total freight cost given a limited number of rented containers. To solve the problem efficiently for practical implementation, we propose a new large-scale neighborhood search heuristic. The proposed large-scale neighborhood relaxes the subset-disjoint restriction made in the existing literature; the relaxation risks a possibility of infeasible exchanges while at the same time it avoids the potentially large amount of checking effort required to enforce the subset-disjoint restriction. An efficient procedure is then used to search for improvement in the neighborhood. We have also proposed a subproblem to address the difficulties caused by the fixed charges. The compromised large-scale neighborhood (CLSN) search heuristic has shown stably superior performance when compared with the traditional large-scale neighborhood search and the mixed integer programming model.
12497271
Inequivalent manifold ranking for content-based image retrieval
We propose to improve the effectiveness and scalability of graph based manifold ranking methods in image retrieval applications by emphasizing reliable images while damping the effect of noisy or irregular ones. Label information is firstly passed between most reliable data points, then propagated to less reliable ones on manifold structure. By treating these images inequivalently, undesirable effect of noisy samples is greatly reduced, thus effectiveness of manifold ranking algorithms is enhanced. Also, graph size in terms of number of nodes and edges is dramatically reduced, resulting in a great speed-up of the algorithm. Our experiment on real world image data set demonstrates the effectiveness of the proposed approach.
11690157
Graph and Topological Structure Mining on Scientific Articles
In this paper, we investigate a new approach for literature mining. We use frequent subgraph mining, and its generalization topological structure mining, for finding interesting relationships between gene names and other key biological terms from the text of scientific articles. We show how we can find keywords of interest and represent them as nodes of the graphs. We also propose several methods for inserting edges between these nodes. Our study initially focused on comparing: 1) different methods for constructing edges, and 2) patterns found from sub-graph mining and topological structure mining. Subsequently, we analyzed several frequent topological minors reported by our experiments, and explained their scientific significance. Overall, our study shows the following. First, a simple method of constructing edges, which is based on sliding windows, seems to provide the best results. Second, we are able to find much larger number of well-known and meaningful topological patterns with high support values, as compared to sub-graphs. Overall, the frequent topological minors our algorithm found correspond well to known relationships between genes and biological terms. Thus, we believe that topological structure mining can be a very valuable tool for researchers who are not deeply familiar with the existing literature, and want to obtain a quick summary about known relationships among key scientific names or terms.
26734510
Estimate Test Execution Effort at an Early Stage: An Empirical Study
Software testing is becoming more and more important as it is a widely used activity to ensure software quality. Test execution becomes an activity in the critical path of a project. In this case, early estimation of test execution effort can benefit both tester managers and software projects. This paper reports an empirical study on early test execution effort estimation. In the study, we propose an approach which mainly consists of two parts: test case number prediction from use cases and test effort estimation based on the test suite execution vector model which combines test case number, test execution complexity and its tester together. For each part, we evaluate it with the data of real projects from a financial software company.
19880347
Personality Based Latent Friendship Mining
Methods and apparatus for detecting imperfections in adhesive coatings formed on fingers of beams are disclosed. The present invention relates, in one aspect, to a method for preparing a first work piece for joining with a second work piece. The method involves forming a finger in the first work piece, then applying an adhesive coating on the finger. A determination is made to determine whether the adhesive coating is defective through the used of a sensing mechanism which is arranged to scan across a portion of the finger. In one embodiment, a defect in the adhesive coating on the finger is defined as a void.
32208283
A Bidirectional Adaptive Sequential Gaussian Approximation for MIMO Systems
A bidirectional adaptive detection method was proposed to prevent error propagation based on sequential Gaussian approximation algorithm for MIMO systems. Conventional sequential Gaussian approximation detection executes a tree search at the receiver, when the number of searching paths is large, error propagation is well prevented at the cost of high complexity, when few paths are searched, serious error propagation may occur. In the new method, transmitted symbols were estimated parallel both in sequential order and inverse order, and the number of searching paths was determined by comparing the results of bidirectional detection, which can effectively prevent error propagation at reduced complexity. The novel algorithm can be executed at low delay because of parallel computing, and shows good performance at low complexity.