Meta-heuristics for robust graph coloring problem
In This work, the robust graph coloring problem (RGCP), an extension of the classical graph coloring, is solved by various meta-heuristics. After discussing the search space encoding and neighborhood structure, several meta-heuristics including genetic algorithm, simulated annealing and tabu search are developed to solve RGCP. The experimental results on various sizes of input graph provide the performance of these meta-heuristics in terms of accuracy and run time.

title: Meta-heuristic Algorithm for the Transshipment Problem with Fixed Transportation Schedules
abstract: 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.

title: A Compromised Large-Scale Neighborhood Search Heuristic for Cargo Loading Planning
abstract: 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.

title: k-Center Problems with Minimum Coverage
abstract: 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 .

title: A stochastic beam search for the berth allocation problem
abstract: 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.

title: A compromised large-scale neighborhood search heuristic for capacitated air cargo loading planning
abstract: 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.

title: Short-Term Traffic Flow Prediction Based on Parallel Quasi-Newton Neural Network
abstract: Identifying and predicting the situation of traffic flow play an important role in traveler information broadcast and real-time traffic control. In this paper, a short-term traffic flow prediction model based on the parallel self-scaling quasi-Newton (SSPQN) neural network is presented. In this method, a set of parallel search directions are generated at the beginning of each iteration. Each of these directions is selectively chosen from a representative class of quasi-Newton (QN) methods. Inexact line searches are then carried out to estimate the minimum point along each search direction. Experimental and analytical results demonstrate the feasibility of applying SSPQN to traffic flow prediction and prove that it can better satisfy real-time demand of traffic flow prediction.

title: Graph and Topological Structure Mining on Scientific Articles
abstract: 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.

title: Personality Based Latent Friendship Mining
abstract: 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.

title: An Adaptive MIMO System Based on Unified Belief Propagation Detection
abstract: An adaptive multiple input and multiple output (MIMO) system based on the unified belief propagation (BP) detection is proposed. A BP detector composed of a serial of component detectors is first presented. With a unified design of the BP detector, a multi-rate MIMO system adaptive to channel variations is then developed, which aims at achieving the maximal throughput performance. The usage of the unified BP detector eliminates the multiple detector modules at the receiver in conventional multi-mode adaptive MIMO systems. Further, the linear complexity to space time block length and parallel operation of the unified BP detection provide the advantages of low complexity, low detection delay and smooth switching between different data rates. With the average receiving signal-to-noise ratio (SNR) based switching mechanism, the proposed adaptive MIMO framework adaptively chooses the appropriate rate for the transmission. Simulation results are provided to show the BER and complexity performance of a specific BP detector as well as the throughput performance of the adaptive scheme.

title: On the competitiveness of on-line real-time task scheduling
abstract: With respect to on-line scheduling algorithms that must direct the service of sporadic task requests we quantify the benefit of clairvoyancy, i.e., the power of possessing knowledge of various task parameters of future events. Specifically, we consider the problem of preemptively sheduling sporadic task requests in both uni- and multi-processor environments. If a task request is successfuly scheduled to completion, a value equal to the task's execution time is obtained; otherwise no value is obtained. We prove that no on-line scheduling algorithm can guarantee a cumulative value greater than 1/4th the value obtainable by a clairvoyant scheduler; i.e., we prove a 1/4th upper bound on the competitive factor of on-line real-time schedulers. We present an online uniprocessor scheduling algorithm TD1 that actually has a competitive factor of 1/4; this bound is thus shown to be tight. We further consider the effect of restricting the amount of overloading permitted (the loading factor), and quantify the relationship between the loading factor and the upper bound on the competitive factor. Other results of a similar nature deal with the effect of value densities (measuring the importance of type of a task). Generalizations to dual-processor on-line scheduling are also considered. For the dual-processor case, we prove an upper bound of 1/2 on the competitive factor. This bound is shown to be tight in the special case when all the tasks have the same density and zero laxity.