An exact method for graph coloring

We are interested in the graph coloring problem. We propose an exact method based on a linear-decomposition of the graph. The complexity of this method is exponential according to the linearwidth of the entry graph, but linear according to its number of vertices. We present some experiments performed on literature instances, among which COLOR02 library instances. Our method is useful to solve more quickly than other exact algorithms instances with small linearwidth, such as mug graphs. Moreover, our algorithms are the first to our knowledge to solve the COLOR02 instance 4-Inser_3 with an exact method.     

A Memetic Algorithm for staff scheduling problem in airport security service

The staff scheduling problem is widely studied in Operational Research. Various surveys are available in the literature dealing with this problem which concerns various objectives and various constraints. In this article, we present a staff scheduling problem in airport security service. First, a modeling of the problem, and a representation of solutions are shown. The problem is solved in three steps, days-off scheduling, shift scheduling, and staff assignment. We focus on the last step, by providing a Memetic Algorithm (MA) which merged an Evolutionary Algorithm and Local Search techniques. We propose a chromosome encoding, a crossover operator and a combined neighborhood function, specially dedicated to this staff assignment problem. Besides providing better solutions than software currently used, this algorithm provides up to 50% of improvement from initial feasible solutions.     

Best practices for comparing optimization algorithms

Comparing, or benchmarking, of optimization algorithms is a complicated task that involves many subtle considerations to yield a fair and unbiased evaluation. In this paper, we systematically review the benchmarking process of optimization algorithms, and discuss the challenges of fair comparison. We provide suggestions for each step of the comparison process and highlight the pitfalls to avoid when evaluating the performance of optimization algorithms. We also discuss various methods of reporting the benchmarking results. Finally, some suggestions for future research are presented to improve the current benchmarking process.     

Evaluating Network Reliability and 2-Edge-Connected Reliability in Linear Time for Bounded Pathwidth Graphs

This paper presents a decomposition method for computing the 2-edge-connected reliability of undirected networks. This reliability is defined as the probability that all the vertices of a given graph G are 2-edge-connected, when edges fail independently with known probabilities. The principle of this method was introduced by Rosenthal in 1977 [1]. For the all terminal reliability problem it consists in enumerating specific state classes of some subnetworks. These classes are represented by the partitions of the boundary sets. For the 2-edge-connected reliability problem these classes are represented by labeled forests whose nodes are the partition blocks and some ``unidentified' blocks. Our implementation uses a vertex linear ordering. The computational complexity depends on the number of classes, which depends on the vertex separation number of a given vertex linear ordering. Our computational results show the efficiency of this method when the vertex separation number is smaller than 7.     

Sustained ventricular tachycardia in older children. Spontaneous regression in 3 cases]

Extensively described since Gallvardin's reports, the electrical features of salves of ventricular tachycardia in an apparently healthy heart are now well known. The usual benign nature of this arrhythmia is acknowledged, seldom contradicted by isolated clinical cases. Although chronicity is the rule in young adults, there have been a few publications concerning the natural history of these tachycardias in the paediatric age group. The authors report three cases of episodic sustained ventricular tachycardia in older children, presenting at an average of 7 years of age (range 5 to 9 years) and followed up for an average of 7 years (range: 5.5 to 9 years). These three children were treated for an average of 4.5 years (range: 3 to 5.5 years). All treatment was finally withdrawn when stable permanent sinus rhythm without ventricular extrasystoles was restored and confirmed over an average period of 2 years (range 10 months to 3.5 years), an average of 4 (range 3 to 7) successive normal Holter recordings at several months' interval. The outcome in children to spontaneous regression after several years would seem to make radiofrequency ablation more dangerous than useful given the benign nature of the arrhythmia and its good response to pharmacological intervention.     

New sequential exact Euclidean distance transform algorithms based on convex analysis

We present several sequential exact Euclidean distance transform algorithms. The algorithms are based on fundamental transforms of convex analysis: The Legendre Conjugate or Legendre–Fenchel transform, and the Moreau envelope or Moreau-Yosida approximate. They combine the separability of the Euclidean distance with convex properties to achieve an optimal linear-time complexity.We compare them with a Parabolic Envelope distance transform, and provide several extensions. All the algorithms presented perform equally well in higher dimensions. They can naturally handle grayscale images, and their principles are generic enough to apply to other transforms.     

Variable neighborhood search for a planning problem with resource constraints in a health simulation center

Applied Intelligence - In this paper we propose the Variable Neighborhood Search (VNS) algorithm SimULS to solve a planning problem in the Health Simulation Center SimUSanté. This center...