Tight analysis of the (1+1)-EA for the single source shortest path problem

We conduct a rigorous analysis of the (1+1) evolutionary algorithm for the single source shortest path problem proposed by Scharnow, Tinnefeld, and Wegener (The analyses of evolutionary algorithms on sorting and shortest paths problems, 2004, Journal of Mathematical Modelling and Algorithms, 3(4):349-366). We prove that with high probability, the optimization time is O(n2 max{?, log(n)}), where ? is the smallest integer such that any vertex can be reached from the source via a shortest path having at most ? edges. This bound is tight. For all values of n and ? we provide a graph with edge weights such that, with high probability, the optimization time is of order Ω(n2 max{?, log(n)}). To obtain such sharp bounds, we develop a new technique that overcomes the coupon collector behavior of previously used arguments. Also, we exhibit a simple Chernoff type inequality for sums of independent geometrically distributed random variables, and one for sequences of random variables that are not independent, but show a desired behavior independent of the outcomes of the previous random variables. We are optimistic that these tools find further applications in the analysis of evolutionary algorithms.     

GPU-based real-time approximation of the ablation zone for radiofrequency ablation

Percutaneous radiofrequency ablation (RFA) is becoming a standard minimally invasive clinical procedure for the treatment of liver tumors. However, planning the applicator placement such that the malignant tissue is completely destroyed, is a demanding task that requires considerable experience. In this work, we present a fast GPU-based real-time approximation of the ablation zone incorporating the cooling effect of liver vessels. Weighted distance fields of varying RF applicator types are derived from complex numerical simulations to allow a fast estimation of the ablation zone. Furthermore, the heat-sink effect of the cooling blood flow close to the applicator's electrode is estimated by means of a preprocessed thermal equilibrium representation of the liver parenchyma and blood vessels. Utilizing the graphics card, the weighted distance field incorporating the cooling blood flow is calculated using a modular shader framework, which facilitates the real-time visualization of the ablation zone in projected slice views and in volume rendering. The proposed methods are integrated in our software assistant prototype for planning RFA therapy. The software allows the physician to interactively place virtual RF applicator models. The real-time visualization of the corresponding approximated ablation zone facilitates interactive evaluation of the tumor coverage in order to optimize the applicator's placement such that all cancer cells are destroyed by the ablation.     

Distance visualization for interactive 3D implant planning

An instant and quantitative assessment of spatial distances between two objects plays an important role in interactive applications such as virtual model assembly, medical operation planning, or computational steering. While some research has been done on the development of distance-based measures between two objects, only very few attempts have been reported to visualize such measures in interactive scenarios. In this paper we present two different approaches for this purpose, and we investigate the effectiveness of these approaches for intuitive 3D implant positioning in a medical operation planning system. The first approach uses cylindrical glyphs to depict distances, which smoothly adapt their shape and color to changing distances when the objects are moved. This approach computes distances directly on the polygonal object representations by means of ray/triangle mesh intersection. The second approach introduces a set of slices as additional geometric structures, and uses color coding on surfaces to indicate distances. This approach obtains distances from a precomputed distance field of each object. The major findings of the performed user study indicate that a visualization that can facilitate an instant and quantitative analysis of distances between two objects in interactive 3D scenarios is demanding, yet can be achieved by including additional monocular cues into the visualization.     

An algebraic foundation for automatic feature-based program synthesis

Feature-Oriented Software Development provides a multitude of formalisms, methods, languages, and tools for building variable, customizable, and extensible software. Along different lines of research, different notions of a feature have been developed. Although these notions have similar goals, no common basis for evaluation, comparison, and integration exists. We present a feature algebra that captures the key ideas of feature orientation and that provides a common ground for current and future research in this field, on which also alternative options can be explored. Furthermore, our algebraic framework is meant to serve as a basis for the development of the technology of automatic feature-based program synthesis and architectural metaprogramming.     

Efficient estimation of a semiparametric dynamic copula model

A new semiparametric dynamic copula model is proposed where the marginals are specified as parametric GARCH-type processes, and the dependence parameter of the copula is allowed to change over time in a nonparametric way. A straightforward two-stage estimation method is given by local maximum likelihood for the dependence parameter, conditional on consistent first stage estimates of the marginals. First, the properties of the estimator are characterized in terms of bias and variance and the bandwidth selection problem is discussed. The proposed estimator attains the semiparametric efficiency bound and its superiority is demonstrated through simulations. Finally, the wide applicability of the model in financial time series is illustrated, and it is compared with traditional models based on conditional correlations.     

Computing delay resistant railway timetables

In the past, much research has been dedicated to compute optimum railway timetables. A typical objective has been the minimization of passenger waiting times. But only the planned nominal waiting times have been addressed, whereas delays as they occur in daily operations have been neglected. Delays have been rather treated mainly in an online context and solved as a separate optimization problem, called delay management.We provide the first computational study which aims at computing delay resistant periodic timetables. In particular we assess the delay resistance of a timetable by evaluating it subject to several delay scenarios to which optimum delay management will be applied.We arrive at computing delay resistant timetables by selecting a new objective function which we design to be somehow in the middle of the traditional simple timetabling objective and the sophisticated delay management objective. This is a slight extension of the concept of “light robustness” (LR) as it has been proposed by Fischetti and Monaci [2006. Robust optimization through branch-and-price. In: Proceedings of AIRO]. Moreover, in our application we are able to provide accurate interpretations for the ingredients of LR. We apply this new technique to real-world data of a part of the German railway network of Deutsche Bahn AG. Our computational results suggest that a significant decrease of passenger delays can be obtained at a relatively small price of robustness, i.e. by increasing the nominal travel times of the passengers.     

Spatially Varying Mixtures Incorporating Line Processes for Image Segmentation

Spatially varying mixture models are characterized by the dependence of their mixing proportions on location (contextual mixing proportions) and they have been widely used in image segmentation. In this work, Gauss-Markov random field (MRF) priors are employed along with spatially varying mixture models to ensure the preservation of region boundaries in image segmentation. To preserve region boundaries, two distinct models for a line process involved in the MRF prior are proposed. The first model considers edge preservation by imposing a Bernoulli prior on the normally distributed local differences of the contextual mixing proportions. It is a discrete line process model whose parameters are computed by variational inference. The second model imposes Gamma prior on the Student’s-t distributed local differences of the contextual mixing proportions. It is a continuous line process whose parameters are also automatically estimated by the Expectation-Maximization (EM) algorithm. The proposed models are numerically evaluated and two important issues in image segmentation by mixture models are also investigated and discussed: the constraints to be imposed on the contextual mixing proportions to be probability vectors and the MRF optimization strategy in the frameworks of the standard and variational EM algorithm.