0000000000003083
AUTHOR
Wolfgang Steitz
Orientation matters
The optimal communication spanning tree (OCST) problem is a well known $\mathcal{NP}$-hard combinatorial optimization problem which seeks a spanning tree that satisfies all given communication requirements for minimal total costs. It has been shown that optimal solutions of OCST problems are biased towards the much simpler minimum spanning tree (MST) problem. Therefore, problem-specific representations for EAs like heuristic variants of edge-sets that are biased towards MSTs show high performance.In this paper, additional properties of optimal solutions for Euclidean variants of OCST problems are studied. Experimental results show that not only edges in optimal trees are biased towards low-…
Inferring Decision Strategies from Clickstreams in Decision Support Systems: A New Process-Tracing Approach using State Machines
The importance of online shopping has grown remarkably over the last decade. In 2009, every West European spent on average € 483 online and this amount is expected to grow to € 601 in 2014. In Germany, the number of online shoppers has almost doubled since 2000: 44% of all adults regularly buy products onlinetoday. In Western Europe, online sales reached € 68 billion in 2009 and Forrester research forecasts it will reach € 114 billion by 2014 with an 11% compound annual growth rate.
Edge Orientation and the Design of Problem-Specific Crossover Operators for the OCST Problem
In the Euclidean optimal communication spanning tree problem, the edges in optimal trees not only have small weights but also point with high probability toward the center of the graph. These characteristics of optimal solutions can be used for the design of problem-specific evolutionary algorithms (EAs). Recombination operators of direct encodings like edge-set and NetDir can be extended such that they prefer not only edges with small distance weights but also edges that point toward the center of the graph. Experimental results show higher performance and robustness in comparison to EAs using existing crossover strategies.
Code-share connectivity within global airline alliances – How much potential is utilized?
Abstract This paper analyzes the code-share connectivity of carriers from the three global alliances: Star Alliance, Sky Team and oneworld. We generate 2-leg online and code-share connections to evaluate the existing connectivity. Additionally, we generate all potential interline connections between members of the same alliance that are not yet supported with existing code-shares and analyze what share of the potential connectivity remains unused. We find that code-share connections account to about one-fourth of the total number of international connections offered by alliance members. 73% of those code-share connections are with partners from the same alliance, 6% with carriers from compe…
Using penalties instead of rewards: Solving OCST problems with guided local search
Abstract This paper considers the optimal communication spanning tree (OCST) problem. Previous work analyzed features of high-quality solutions and found that edges in optimal solutions have low weight and point towards the center of a tree. Consequently, integrating this problem-specific knowledge into a metaheuristic increases its performance for the OCST problem. In this paper, we present a guided local search (GLS) approach which dynamically changes the objective function to guide the search process into promising areas. In contrast to traditional approaches which reward promising solution features by favoring edges with low weights pointing towards the tree’s center, GLS penalizes low-…
Guided local search for the optimal communication spanning tree problem
This paper considers the optimal communication spanning tree (OCST) problem. Previous work analyzed features of high-quality solutions. Consequently, integrating this knowledge into a metaheuristic increases its performance for the OCST problem. In this paper, we present a guided local search (GLS) approach which dynamically changes the objective function to guide the search process into promising areas. In contrast to traditional approaches which reward promising solution features by favoring edges with low weights pointing towards the tree's center, GLS penalizes low-quality edges with large weights that do not point towards the tree's center.
New insights into the OCST problem
This paper considers the Euclidean variant of the optimal communciation spanning tree (OCST) problem. Researches have analyzed the structure of the problem and found that high quality solutions prefer edges of low cost. Further, edges pointing to the center of the network are more likely to be included in good solutions. We add to the literature and provide additional insights into the structure of the OCST problem. Therefore, we investigate properies of the whole tree, such as node degrees and the Wiener index. The results reveal that optimal solutions are structured in a star-like manner. There are few nodes with high node degrees, these nodes are located next to the graph's center. The m…