with only slight deviations from the actual numbers.

},
author = {Rabani, Yuval and Sinclair, Alistair and Wanka, Rolf},
booktitle = {Proc. 39th IEEE Symposium on Foundations of Computer Science (FOCS)},
doi = {10.1109/SFCS.1998.743520},
faupublication = {no},
pages = {694-703},
title = {{Local} {Divergence} of {Markov} {Chains} and the {Analysis} of {Iterative} {Load}-{Balancing} {Schemes}},
venue = {San Francisco, USA},
year = {1998}
}
@inproceedings{faucris.119723604,
author = {Mühlenthaler, Moritz and Wanka, Rolf},
booktitle = {Proc. 9th Int. Conf. on the Practice and Theory of Automated Timetabling (PATAT)},
date = {2012-08-28/2012-08-31},
faupublication = {yes},
note = {UnivIS-Import:2015-04-16:Pub.2012.tech.IMMD.infalg._fairn},
pages = {114-130},
title = {{Fairness} in {Academic} {Timetabling}},
venue = {Son},
year = {2012}
}
@inproceedings{faucris.123478564,
abstract = {We present the analysis of a discrete particle swarm optimization (PSO) algorithm that works on a significantly large class of discrete optimization problems. Assuming a black-box setting, we prove upper and lower bounds on the expected number of function evaluations required by the proposed algorithm to solve the sorting problem and the problem of maximizing the number of ones in a bitstring, i.e., the function OneMax. We show that depending on the probability of moving towards the attractor, the expected optimization time may be polynomial or exponential. The cornerstone of our analysis are Theta-bounds on the expected time it takes until the PSO returns to the attractor. We obtain these bounds by solving linear recurrence equations with constant and non-constant coefficients. We also introduce a useful indistinguishability property of states of a Markov chain in order to obtain lower bounds on the expected optimization time of our proposed PSO algorithm.},
author = {Mühlenthaler, Moritz and Raß, Alexander and Schmitt, Manuel and Siegling, Andreas and Wanka, Rolf},
booktitle = {Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms},
date = {2017-01-12/2017-01-15},
doi = {10.1145/3040718.3040721},
editor = {ACM New York, NY, USA},
faupublication = {yes},
isbn = {978-1-4503-4651-1},
keywords = {Particle Swarm Optimization; Discrete Optimization; Run-time Analysis; Markov Chains},
month = {Jan},
pages = {13-24},
peerreviewed = {unknown},
title = {{Runtime} {Analysis} of a {Discrete} {Particle} {Swarm} {Optimization} {Algorithm} on {Sorting} and {OneMax}},
venue = {Copenhagen, Denmark},
year = {2017}
}
@incollection{faucris.203699174,
address = {Berlin Heidelberg},
author = {Wanka, Rolf},
booktitle = {Taschenbuch der Algorithmen},
doi = {10.1007/978-3-540-76394-9_4},
editor = {Vöcking B},
faupublication = {yes},
isbn = {978-3-540-76393-2},
note = {UnivIS-Import:2018-09-06:Pub.2008.tech.IMMD.inform.parall},
pages = {31-41},
peerreviewed = {unknown},
publisher = {Springer},
title = {{Paralleles} {Sortieren} - {Parallel} geht schnell},
year = {2008}
}
@article{faucris.106483784,
abstract = {A parallel processor network is called n-universal with slowdown s if it can simulate each computation of each constant-degree processor network with n processors with slowdown s. We prove the following lower bound tradeoff: for each constant-degree n-universal network of size m with slowdown s,m·s = Ω(n log m) holds. Our tradeoff holds for a very general model of simulations. It covers all previously considered models and all known techniques for simulations among networks. For m ≥ n, this improves a previous lower bound by a factor of log log n, proved for a weaker simulation model. For m ≥ n, this is the first nontrivial lower bound for this problem. In this case this lower bound is asymptotically tight.},
author = {Wanka, Rolf and Meyer auf der Heide, Friedhelm and Storch, Martin},
doi = {10.1007/s002240000071},
faupublication = {no},
journal = {Theory of Computing Systems},
pages = {627-644},
peerreviewed = {Yes},
title = {{Optimal} tradeoffs between size and slowdown for universal parallel networks},
volume = {30},
year = {1997}
}
@inproceedings{faucris.110076384,
author = {Bonorden, Olaf and Meyer auf der Heide, Friedhelm and Wanka, Rolf},
booktitle = {Proceedings of the Int. Conf. on Parallel and Distributed Processing Techniques and Applications (PDPTA)},
faupublication = {no},
pages = {2202-2208; 2002},
peerreviewed = {unknown},
title = {{Composition} of {Efficient} {Nested} {BSP} {Algorithms}: {Minimum} {Spanning} {Tree} {Computation} as an {Instructive} {Example}},
year = {2002}
}
@inproceedings{faucris.118485224,
abstract = {We propose a generic, hybrid constraint handling scheme for particle swarm optimization called Heterogeneous Constraint Handling. Inspired by the notion of social roles, we assign different constraint handling methods to the particles, one for each social role. In this paper, we investigate two social roles for particles, 'self' and 'neighbor'. Due to the usual particle dynamics, a powerful mixture of the two corresponding constraint handling methods emerges. We evaluate this heterogeneous constraint handling approach with respect to the complete set of the CEC 2006 benchmark instances. Our results indicate that a such a heterogeneous combination of two constraint handling methods often leads to significantly better results than running each individual constraint handling method separately and returning the best solution obtained. © 2011 IEEE.},
address = {New York, NY, USA},
author = {Omeltschuk, Ludmila and Helwig, Sabine and Mühlenthaler, Moritz and Wanka, Rolf},
booktitle = {Proc. IEEE Swarm Intelligence Symposium (SIS)},
date = {2011-04-11/2011-04-15},
doi = {10.1109/SIS.2011.5952578},
faupublication = {yes},
isbn = {978-1-61284-053-6},
note = {UnivIS-Import:2015-04-16:Pub.2011.tech.IMMD.infalg._heter},
pages = {37-43},
publisher = {IEEE Press},
title = {{Heterogeneous} {Constraint} {Handling} for {Particle} {Swarm} {Optimization}},
venue = {Paris},
year = {2011}
}
@inproceedings{faucris.107183604,
author = {Kutylowski, Miroslaw and Wanka, Rolf},
booktitle = {In Proc. of 8th International Symposium on Algorithms and Computation (ISAAC)},
faupublication = {no},
pages = {32-41},
peerreviewed = {unknown},
title = {{Playing} {Tetris} on {Meshes} and {Multi}-{Dimensional} {SHEARSORT}},
year = {1997}
}
@incollection{faucris.119079884,
abstract = {Swarm Intelligence methods have been shown to produce good results in various problem domains. A well-known method belonging to this kind of algorithms is particle swarm optimization (PSO). In this chapter, we examine how adaptation mechanisms can be used in PSO algorithms to better deal with continuous optimization problems. In case of bound-constrained optimization problems, one has to cope with the situation that particles may leave the feasible search space. To deal with such situations, different bound handling methods were proposed in the literature, and it was observed that the success of PSO algorithms highly depends on the chosen bound handling method. We consider how velocity adaptation mechanisms can be used to cope with bounded search spaces. Using this approach we show that the bound handling method becomes less important for PSO algorithms and that using velocity adaptation leads to better results for a wide range of benchmark functions.},
address = {Heidelberg},
author = {Helwig, Sabine and Neumann, Frank and Wanka, Rolf},
booktitle = {Handbook of Swarm Intelligence},
doi = {10.1007/978-3-642-17390-5_7},
faupublication = {yes},
note = {UnivIS-Import:2015-04-20:Pub.2011.tech.IMMD.infalg._veloc},
pages = {155-173},
peerreviewed = {Yes},
publisher = {Springer},
series = {Adaptation, Learning, and Optimization (ALO)},
title = {{Velocity} {Adaptation} in {Particle} {Swarm} {Optimization}},
url = {https://www12.cs.fau.de/people/rwanka/publications/HNW11.php},
volume = {8},
year = {2011}
}
@inproceedings{faucris.118703464,
abstract = {We study the frequently observed phenomenon of stagna- tion in the context of particle swarm optimization (PSO). We show that in certain situations the particle swarm is likely to move almost parallel to one of the axes, which may cause stagnation. We provide an experimentally supported explanation in terms of a potential of the swarm and are therefore able to adapt the PSO algorithm slightly such that this weakness can be avoided.},
author = {Schmitt, Manuel and Wanka, Rolf},
booktitle = {Companion of Proc. 15th Genetic and Evolutionary Computation Conference},
date = {2013-07-06/2013-07-10},
doi = {10.1145/2464576.2464583},
faupublication = {yes},
keywords = {Particle swarm optimization; Potential; Stagnation},
note = {UnivIS-Import:2015-04-16:Pub.2013.tech.IMMD.infalg._parti_9},
pages = {17-18},
title = {{Particles} {Prefer} {Walking} {Along} the {Axes}: {Experimental} {Insights} into the {Behavior} of a {Particle} {Swarm}},
venue = {Amsterdam},
year = {2013}
}
@inproceedings{faucris.106460684,
abstract = {We analyze evolving tree computations on circulant (rings with "regular" chords) and related graphs. In an evolving α-ary tree computation, a complete tree grows level by level, i. e., every leaf generates α new nodes that become the new leaves. The load balancing task is to spread the new nodes on a network of processors in the moment they were created in such a way that the accumulated number of nodes per processor, i. e., its load, is as close as possible to the average number of nodes per processor. Gao/Rosenberg [2] introduced evolving computations and investigated the growth of complete binary trees on rings of processors. They showed that the so-called ks-regimen behaves optimally in the course of long computations. In this paper, we generalize evolving computations to trees of arbitrary degree and we generalize the regimen notion. We show that any regimen behaves optimally. For this purpose, we model the actual load distribution, the generation process, and the distribution regimen by formal infinite polynomials. Then we show that evaluating these polynomials for certain inputs leads to the analysis of these regimens on circulant and related graphs. It is shown that any regimen leads to a close to optimal load distribution. © Springer-Verlag Berlin Heidelberg 2002.},
author = {Wanka, Rolf},
booktitle = {Proc. 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)},
doi = {10.1007/3-540-36379-3_36},
faupublication = {no},
isbn = {9783540003311},
pages = {413-420},
publisher = {Springer Verlag},
title = {{Any} load-balancing regimen for evolving tree computations on circulant graphs is asymptotically optimal},
venue = {Cesky Krumlov},
year = {2002}
}
@inproceedings{faucris.209630031,
abstract = {We mathematically analyze a discrete particle swarm optimization (PSO) algorithm solving the single-source shortest path (SSSP) problem. Key features are an improved and extended study on Markov chains expanding the adaptability of this technique and its application on the ubiquitous SSSP problem. The results are upper and lower bounds on the expected optimization time. For upper bounds, we combine return times within a Markov model with the well known fitness level method which is appropriate even for the non-elitist PSO algorithm. For lower bounds we prove that the recently introduced property of indistinguishability applies in this setting and we also combine it with a further Markov chain analysis.},
address = {Cham},
author = {Raß, Alexander and Schreiner, Jonas and Wanka, Rolf},
booktitle = {Evolutionary Computation in Combinatorial Optimization},
date = {2019-04-24/2019-04-26},
doi = {10.1007/978-3-030-16711-0_8},
editor = {Springer International Publishing},
faupublication = {yes},
isbn = {978-3-030-16711-0},
keywords = {Discrete Particle Swarm Optimization; Runtime Analysis; Single-Source Shortest Paths; Markov Chains},
pages = {115-130},
peerreviewed = {unknown},
title = {{Runtime} {Analysis} of {Discrete} {Particle} {Swarm} {Optimization} {Applied} to {Shortest} {Paths} {Computation}},
venue = {Leipzig},
year = {2019}
}
@inproceedings{faucris.106483124,
abstract = {Modern networked embedded system design has to cope with multiple design objectives. One major challenge is the determination of optimal routings with respect to these objectives. Existing automatic optimization approaches carry out a two step optimization: First, they perform a multi-objective topology optimization of the networked embedded system. Then, a multi-objective routing optimization for a subset of Pareto-optimal solutions obtained from the first step is performed. In general, this may exclude several globally optimal solutions from the optimization process. To overcome this drawback, a unified approach based on Multi-Objective Evolutionary Algorithms is presented that ensures a combined optimization of the topology and routing. Since the system topology is varied within the optimization, the main contribution of this paper contribution is a novel routing technique that always samples feasible paths using a topology independent genetic encoding. This encoding preserves optimized routing information when changing the underlying topology. An experimental evaluation shows the effectiveness of the presented approach.},
author = {Glaß, Michael and Lukasiewycz, Martin and Wanka, Rolf and Haubelt, Christian and Teich, Jürgen},
booktitle = {Proc. 8th Int. Conf. on Embedded Computer Systems: Architectures, Modeling, and Simulation (IC-SAMOS)},
doi = {10.1109/ICSAMOS.2008.4664849},
faupublication = {yes},
isbn = {9781424419852},
pages = {74-81},
title = {{Multi}-objective routing and topology optimization in networked embedded systems},
venue = {Samos},
year = {2008}
}
@inproceedings{faucris.106486864,
abstract = {Application details uncertain at design time as well as tolerance against permanent resource defects demand flexibility and redundancy. In this context, we present a strategy for placing replicas in embedded point-to-point networks where link as well as node defects may occur at runtime. The proposed strategies for replica placement are based on the partitioning of the network into biconnected components. We are able to distinguish between different replication strategies, i.e., active and passive replication. Our experimental results show that the reliability improvement due to the proposed replica placement strategies is up to 23% compared to a randomized strategy. © 2008 Springer-Verlag Berlin Heidelberg.},
author = {Streichert, Thilo and Glaß, Michael and Wanka, Rolf and Haubelt, Christian and Teich, Jürgen},
booktitle = {Proc. 21st International Conference on Architecture of Computing Systems (ARCS)},
date = {2008-02-25/2008-02-28},
doi = {10.1007/978-3-540-78153-0_4},
faupublication = {yes},
pages = {23-37},
title = {{Topology}-aware replica placement in fault-tolerant embedded networks},
url = {http://www12.cs.fau.de/people/rwanka/publications/SGWHT08.php},
venue = {Dresden},
year = {2008}
}
@inproceedings{faucris.118770784,
abstract = {Particle Swarm Optimization (PSO) is a popular nature-inspired meta-heuristic for solving continuous optimization problems. Although this technique is widely used, the understanding of the mechanisms that make swarms so successful is still limited. We present the first substantial experimental investigation of the influence of the local attractor on the quality of exploration and exploitation. We compare in detail classical PSO with the social-only variant where local attractors are ignored. To measure the exploration capabilities, we determine how frequently both variants return results in the neighborhood of the global optimum. We measure the quality of exploitation by considering only function values from runs that reached a search point sufficiently close to the global optimum and then comparing in how many digits such values still deviate from the global minimum value. It turns out that the local attractor significantly improves the exploration, but sometimes reduces the quality of the exploitation. The effects mentioned can also be observed by measuring the potential of the swarm. © 2014 Springer International Publishing Switzerland.},
author = {Lange, Vanessa and Schmitt, Manuel and Wanka, Rolf},
booktitle = {Proc. International Conference on Adaptive and Intelligent Systems (ICAIS)},
date = {2014-09-08/2014-09-10},
doi = {10.1007/978-3-319-11298-5_10},
faupublication = {yes},
note = {UnivIS-Import:2015-04-16:Pub.2014.tech.IMMD.infalg._towar},
pages = {90-99},
publisher = {Springer Verlag},
title = {{Towards} a {Better} {Understanding} of the {Local} {Attractor} in {Particle} {Swarm} {Optimization}: {Speed} and {Solution} {Quality}},
url = {https://www12.informatik.uni-erlangen.de/people/rwanka/publications/LSW14.php},
venue = {Bournemouth, UK},
year = {2014}
}
@inproceedings{faucris.118365764,
address = {Berlin, Offenbach},
author = {Mühlenthaler, Moritz and Wanka, Rolf},
booktitle = {Proc. 23rd PARS-Workshop on Parallel Systems and Architectures of the 23rd Int. Conf. on Architecture of Computing Systems (ARCS)},
faupublication = {yes},
isbn = {978-3-8007-3222-7},
note = {UnivIS-Import:2015-04-16:Pub.2010.tech.IMMD.infalg._impro},
pages = {15-22},
publisher = {VDE Verlag},
title = {{Improving} {Bitonic} {Sorting} by {Wire} {Elimination}},
url = {http://www12.informatik.uni-erlangen.de/people/rwanka/publications/MW10.php},
venue = {Hannover},
year = {2010}
}
@inproceedings{faucris.121431024,
author = {Meyer auf der Heide, Friedhelm and Wanka, Rolf},
booktitle = {Proceedings of the Int. Conf. on Computational Science (ICCS)},
faupublication = {no},
pages = {628-637},
peerreviewed = {unknown},
title = {{Parallel} {Bridging} {Models} and {Their} {Impact} on {Algorithm} {Design}},
year = {2001}
}
@inproceedings{faucris.118770124,
abstract = {This paper presents a graph-based representation of success trees to evaluate the reliability of an embedded system. First, a success tree is constructed by deriving a characteristic function from a graph-based system model automatically. The constructed success tree is then translated to a graph (called a success graph) which supports both cyclic and acyclic data dependencies in applications to be mapped to the system resources and analyzed for reliability. To analyze the success graph, an algorithm called 0-propagation is introduced which propagates errors through the graph. The system fails if the errors propagate to the output of the success graph. Experimental results show that the proposed technique can simply and efficiently construct and analyze success trees of real-life embedded systems in a short time with negligible inaccuracy which suits well for evaluating the reliability of complex systems, e. g., as part of a design space exploration. © 2014 IEEE.},
author = {Aliee, Hananeh and Glaß, Michael and Wanka, Rolf and Teich, Jürgen},
booktitle = {Proc. 60th Annual Reliability and Maintainability Symposium (RAMS)},
date = {2014-01-27/2014-01-30},
doi = {10.1109/RAMS.2014.6798487},
faupublication = {yes},
keywords = {design space exploration; fault tree; permanent fault; stochastic logic; Success tree; transient fault},
note = {UnivIS-Import:2015-04-16:Pub.2014.tech.IMMD.infalg._autom},
pages = {563-569},
title = {{Automatic} {Graph}-based {Success} {Tree} {Construction} and {Analysis}},
url = {https://www12.informatik.uni-erlangen.de/people/rwanka/publications/AGWT14.php},
venue = {Colorado Springs, Colorado, USA},
year = {2014}
}
@inproceedings{faucris.118484784,
abstract = {Sorting is one of the most investigated tasks computers are used for. Up to now, not much research has been put into increasing the flexibility and performance of sorting applications by applying reconfigurable computer systems. There are parallel sorting algorithms (sorting circuits) which are highly suitable for VLSI hardware realization and which outperform sequential sorting methods applied on traditional software processors by far. But usually they require a large area that increases with the number of keys to be sorted. This drawback concerns ASIC and statically reconfigurable systems. In this paper, we present a way to adopt the well-known Bitonic sorting method to dynamically reconfigurable systems such that this drawback is overcome. We present a detailed description of the design and actual implementation, and we present experimental results of our approach to show its benefits in performance and the trade-offs of our approach. © 2011 IEEE.},
address = {New York, NY, USA},
author = {Angermeier, Josef and Sibirko, Eugen and Wanka, Rolf and Teich, Jürgen},
booktitle = {Proc. IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW)},
date = {2011-05-16/2011-05-20},
doi = {10.1109/IPDPS.2011.164},
faupublication = {yes},
isbn = {978-1-61284-425-1},
note = {UnivIS-Import:2015-04-16:Pub.2011.tech.IMMD.infalg._biton},
pages = {314-317},
publisher = {IEEE Press},
title = {{Bitonic} {Sorting} on {Dynamically} {Reconfigurable} {Architectures}},
venue = {Anchorage, AL},
year = {2011}
}
@inproceedings{faucris.118336064,
abstract = {In order to improve the behavior of Particle Swarm Optimization (PSO), the classical method is often extended by additional operations. Here, we are interested in how much ``PSO" remains in this case, and how often the extension takes over the computation. We study the variant of PSO that applies random velocities (then called forced moves) as soon as the so-called potential of the swarm falls below a certain bound. We show experimentally that the number of iterations the swarm actually deviates from the classical PSO behavior is small as long as the particles are sufficiently far away from any local optimum. As soon as the swarm comes close to a local optimum, the number of forced moves increases significantly and approaches a value that depends on the swarm size and the problem dimension, but not on the actual fitness function, an observation that can be used as a stopping criterion. Additionally, we provide an explanation for the observed phenomenon in terms of the swarms potential.},
author = {Bassimir, Bernd and Schmitt, Manuel and Wanka, Rolf},
booktitle = {Proc. Int. Conf. on Swarm Intelligence Based Optimization (ICSIBO)},
doi = {10.1007/978-3-319-12970-9_11},
faupublication = {yes},
pages = {98-105},
title = {{How} {Much} {Forcing} is {Necessary} to {Let} the {Results} of {Particle} {Swarms} {Converge}?},
url = {http://www12.cs.fau.de/people/rwanka/publications/BSW14.php},
year = {2014}
}
@inproceedings{faucris.108033024,
author = {Jordan, Johannes Michael and Helwig, Sabine and Wanka, Rolf},
booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference},
date = {2008-07-12/2008-07-16},
doi = {10.1145/1389095.1389103},
editor = {ACM Press},
faupublication = {yes},
pages = {49-56},
title = {{Social} {Interaction} in {Particle} {Swarm} {Optimization}, the {Ranked} {FIPS}, and {Adaptive} {Multi}-{Swarms}},
url = {http://www12.informatik.uni-erlangen.de/people/helwig/publications/JHW08.php},
venue = {Atlanta, Georgia},
year = {2008}
}
@inproceedings{faucris.110660264,
author = {Schmitt, Manuel and Wanka, Rolf and Schwab, Lydia},
booktitle = {Proc. 12th IEEE Conf. on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB)},
doi = {10.1109/CIBCB.2015.7300314},
faupublication = {yes},
note = {UnivIS-Import:2015-10-26:Pub.2015.tech.IMMD.infalg._multi},
pages = {403-410},
title = {{Multimodal} {Medical} {Image} {Registration} {Using} {Particle} {Swarm} {Optimization} with {Influence} of the {Data}'s {Initial} {Orientation}},
venue = {Niagara Falls},
year = {2015}
}
@inproceedings{faucris.106485324,
abstract = {We present a comparative study of implementations of the following sorting algorithms on the Parsytec SC320 reconflgurable, asynchronous, massively parallel MIMD machine: Bitonic Sort, Odd-Even Merge Sort, Odd-Even Merge Sort with guarded split&merge. and two variants of Samplesort. The experiments are performed on 2- up to 5-dimensional wrapped butterfly networks with 8 up to 160 processors. We make use of library functions that provide primitives for global variables and synchronization, and we show that it is possible to implement efficient and portable programs easily. In order to predict the performance, we model the runtime of an access to a global variable by a certain trilinear function and the runtime of a synchronization by a certain bilinear function. Our experiments show that, in the context of parallel sorting, this model that can be applied easily is sufficiently detailed to give good runtime predictions. The experiments confirming the predictions point out that Odd-Even Merge Sort with guarded split&merge is the fastest method if the processors hold few keys. If there are many keys per processor, a combination of Samplesort and Odd-Even Merge Sort is the fastest method.},
author = {Wachsmann, Alf and Wanka, Rolf},
booktitle = {Proc 3rd International Conference on Parallel Processing (Euro-Par)},
doi = {10.1007/BFb0002763},
faupublication = {no},
pages = {399-408},
title = {{Sorting} on a massively parallel system using a library of basic primitives: {Modeling} and experimental results},
venue = {Passau},
year = {1997}
}
@inproceedings{faucris.107941284,
author = {Riess, Christian and Strehl, Volker and Wanka, Rolf},
booktitle = {Proc. 10th Workshop on Parallel Systems and Algorithms (PASA) of the 25th Int. Conf. on Architecture of Computing Systems (ARCS)},
editor = {GI},
faupublication = {yes},
pages = {505-516},
title = {{The} {Spectral} {Relation} between the {Cube}-{Connected} {Cycles} and the {Shuffle}-{Exchange} {Network}},
venue = {München},
year = {2012}
}
@inproceedings{faucris.118364004,
author = {Mühlenthaler, Moritz and Wanka, Rolf},
booktitle = {Proc. 8th Int. Conf. on the Practice and Theory of Automated Timetabling (PATAT)},
faupublication = {yes},
note = {UnivIS-Import:2015-04-16:Pub.2010.tech.IMMD.infalg._anove},
pages = {294-304},
title = {{A} {Novel} {Event} {Insertion} {Heuristic} for {Finding} {Feasible} {Solutions} of {Course} {Timetabling} {Problems}},
venue = {Belfast},
year = {2010}
}
@inproceedings{faucris.118360264,
abstract = {This work presents the design and implementation of a massively parallel 3-SAT solver, specifically targeting random problem instances. Our approach is deterministic and features very little communication overhead and basically no load-balancing cost at all. In the context of most current parallel SAT solvers running only on a handful of cores, we implemented our solver on Nvidia's CUDA platform, utilizing more than 200 parallel streaming processors, and employing several millions of threads to work through single problem instances. As most common sequential solver techniques had to be discarded, our approach is additionally supported by a new set of global heuristics, designed specifically to be easily exploited by the underlying thread parallelism. ©2010 IEEE.},
author = {Schönfeld, Fabian and Meyer, Quirin and Stamminger, Marc and Wanka, Rolf},
booktitle = {Proc. High Performance Computing and Simulation Conference (HPSC)},
date = {2010-06-28/2010-07-02},
doi = {10.1109/HPCS.2010.5547116},
faupublication = {yes},
keywords = {GPGPU; Load balancing and sharing; Random 3-SAT; Thread level parallelism},
note = {UnivIS-Import:2015-04-16:Pub.2010.tech.IMMD.IMMD9.3saton},
title = {3-{SAT} on {CUDA}: {Towards} a {Massively} {Parallel} {SAT} {Solver}},
venue = {Caen},
year = {2010}
}
@incollection{faucris.118039064,
address = {Berlin Heidelberg},
author = {Wanka, Rolf},
booktitle = {Taschenbuch der Algorithmen},
doi = {10.1007/978-3-540-76394-9_4},
faupublication = {yes},
isbn = {978-3-540-76393-2},
note = {UnivIS-Import:2015-04-16:Pub.2008.tech.IMMD.infalg._paral},
pages = {31-41},
peerreviewed = {unknown},
publisher = {Springer},
title = {{Paralleles} {Sortieren} - {Parallel} geht schnell},
year = {2008}
}
@inproceedings{faucris.119495464,
abstract = {We investigate the connectedness of clash-free timetables with respect to the Kempe-exchange operation. This investigation is related to the connectedness of the search space of timetabling problem instances, which is a desirable property, for example for twostep algorithms using the Kempe-exchange during the optimization step. The theoretical framework for our investigations is based on the study of reconfiguration graphs, which model the search space of timetabling problems. We contribute to this framework by including period availability requirements in the analysis and we derive improved conditions for the connectedness of clash-free timetables in this setting. We further show that the diameter of the reconfiguration graphs increases only linearly due to the period availability requirements. We apply the theoretical insights to establish the connectedness of clash-free timetables for a number of benchmark instances.},
author = {Mühlenthaler, Moritz and Wanka, Rolf},
booktitle = {Proc. 10th Int. Conf. on the Practice and Theory of Automated Timetabling (PATAT)},
faupublication = {yes},
note = {UnivIS-Import:2015-04-16:Pub.2014.tech.IMMD.infalg._theco},
pages = {330-346},
title = {{The} {Connectedness} of {Clash}-free {Timetables}},
url = {http://www12.cs.fau.de/people/rwanka/publications/MW14.php},
venue = {York, UK},
year = {2014}
}
@article{faucris.113549084,
abstract = {We present an improvement on Thurley's recent randomized approximation scheme for #k-SAT where the task is to count the number of satisfying truth assignments of a Boolean function Φ given as an n-variable k-CNF. We introduce a novel way to identify independent substructures of Φ and can therefore reduce the size of the search space considerably. Our randomized algorithm works for any k. For #3-SAT, it runs in time O(ε- ^{2}×1.51426^{n}), for #4-SAT, it runs in time O(ε-^{2}×1.60816^{n}), with error bound ε. © 2013 Elsevier B.V. All rights reserved.},
author = {Schmitt, Manuel and Wanka, Rolf},
doi = {10.1016/j.ipl.2013.02.013},
faupublication = {yes},
journal = {Information Processing Letters},
keywords = {#k-SAT; Algorithms; Analysis of algorithms; Randomized algorithms; Satisfiability},
note = {UnivIS-Import:2015-03-09:Pub.2013.tech.IMMD.infalg._explo_5},
pages = {337-344},
peerreviewed = {Yes},
title = {{Exploiting} {Independent} {Subformulas}: {A} {Faster} {Approximation} {Scheme} for #k-{SAT}},
volume = {113},
year = {2013}
}
@article{faucris.118434844,
abstract = {We consider comparator networks M that are used repeatedly: while the output produced by M is not sorted, it is fed again into M. Sorting algorithms working in this way are called periodic. The number of parallel steps performed during a single run of M is called 'Us period, the sorting time of M is the total number of parallel steps that are necessary to sort in the worst case. Periodic sprting networks have the advantage that they need little hardware (control logic, wiring, area) and that they are adaptive. We are interested in comparator networks of a constant period, due to their potential applications in hardware design. Previously, very little was known on such networks. The fastest solutions required time O(n), where the depth was roughly 1/∈. We introduce a general method called periodiflcation scheme that converts automatically an arbitrary sorting network that sorts n items in time T(n) and that has layout area A(n) into a sorting network that has period 5, sorts (n · T(n)) items in time O(T(n) · log n), and has layout area O(A(n) ·T(n)). In particular, applying this scheme to Batcher's algorithms, we get practical period 5 comparator networks that sort in time O(log n). For theoretical interest, one may use the AKS network resulting in a period 5 comparator network with runtime 0(log n). © 2000 ACM.},
author = {Kutylowski, Miroslaw and Lorys, Krzysztof and Oesterdiekhoff, Brigitte and Wanka, Rolf},
doi = {10.1145/355483.355490},
faupublication = {no},
journal = {Journal of the Acm},
keywords = {Comparator network},
pages = {944-967},
peerreviewed = {Yes},
title = {{Periodification} scheme: {Constructing} sorting networks with constant period},
volume = {47},
year = {2000}
}
@inproceedings{faucris.106452984,
abstract = {We propose a novel event insertion heuristic for finding feasible solutions for instances of the University Course Timetabling Problem (UCTP). We introduce and apply a new neighbourhood structure on partial timetables that permits to approach a feasible timetable. The key insight is that an event can be inserted in a time slot if all the events conflicting with it are moved to other time slots. In order to prevent our event insertion heuristic from running into local optima, a simple perturbation strategy is employed additionally. Our experimental results show that our event insertion heuristic yields superior results compared to other state-of-The-Art feasible solution generation algorithms for a large number of corresponding benchmark instances.},
author = {Wanka, Rolf and Mühlenthaler, Moritz},
booktitle = {Proc. 8th International Conference on the Practice and Theory of Automated Timetabling (PATAT)},
faupublication = {yes},
keywords = {Course timetabling problems; Feasible solution generation; Kempe move},
pages = {294-304},
title = {{A} novel event insertion heuristic for creating feasible course timetables},
url = {https://www12.informatik.uni-erlangen.de/people/rwanka/publications/MW10b.php},
venue = {Belfast},
year = {2010}
}
@inproceedings{faucris.203368651,
author = {Riess, Christian and Wanka, Rolf},
booktitle = {Proceedings of the 13th International Euro-Par Conference},
date = {2007-08-28/2007-08-31},
doi = {10.1007/978-3-540-74466-5_86},
faupublication = {yes},
pages = {805--814},
peerreviewed = {Yes},
title = {{Periodic} {Load} {Balancing} on the {N}-{Cycle}: {Analytical} and {Experimental} {Evaluation}},
venue = {Rennes},
year = {2007}
}
@inproceedings{faucris.118702144,
abstract = {Particle swarm optimization (PSO) is a popular nature-inspired meta-heuristic for solving continuous optimization problems. Although this technique is widely used, up to now only some partial aspects of the method have been formally investigated. In particular, while it is well-studied how to let the swarm converge to a single point in the search space, no general theoretical statements about this point or on the best position any particle has found have been known. For a very general class of objective functions, we provide for the first time results about the quality of the solution found. We show that a slightly adapted PSO almost surely finds a local optimum. To do so, we investigate the newly defined . potential of the swarm. The potential drops when the swarm approaches the point of convergence, but increases if the swarm remains close to a point that is not a local optimum, meaning that the swarm charges potential and continues its movement.},
author = {Schmitt, Manuel and Wanka, Rolf},
booktitle = {Proc. 15th Genetic and Evolutionary Computation Conference},
doi = {10.1145/2463372.2463563},
faupublication = {yes},
keywords = {Fitness landscapes; Particle swarm optimization; Quality of solution},
note = {UnivIS-Import:2015-04-16:Pub.2013.tech.IMMD.infalg._parti},
pages = {1629-1636},
publisher = {Elsevier},
title = {{Particle} {Swarm} {Optimization} {Almost} {Surely} {Finds} {Local} {Optima}},
venue = {Amsterdam},
year = {2013}
}
@inproceedings{faucris.106485764,
abstract = {We present a new data structure for rendering highly complex virtual environments of arbitrary topology. The special feature of our approach is that it allows an interactive navigation in very large scenes (30 GB/400 million polygons in our benchmark scenes) that cannot be stored in main memory, but only on a local or remote hard disk. Furthermore, it allows interactive rendering of substantially more complex scenes by instantiating objects. For the computation of an approximate image of the scene, a sampling technique is used. In the preprocessing, a so-called sample tree is built whose nodes contain randomly selected polygons from the scene. This tree only uses space that is linear in the number of polygons. In order to produce an image of the scene, the tree is traversed and polygons stored in the visited nodes are rendered. During the interactive walkthrough, parts of the sample tree are loaded from local or remote hard disk. We implemented our algorithm in a prototypical walkthrough system. Analysis and experiments show that the quality of our images is comparable to images computed by the conventional z-buffer algorithm regardless of the scene topology.},
author = {Klein, Jan and Krokowski, Jens and Wand, Michael and Fischer, Matthias and Wanka, Rolf and Meyer auf der Heide, Friedhelm},
booktitle = {Proc. ACM Symp. on Virtual Reality Software and Technology (VRST)},
doi = {10.1145/585740.585764},
editor = {Sun H.; Peng Q.},
faupublication = {no},
keywords = {Level of Detail Algorithms; Monte Carlo Techniques; Out-Of-Core Rendering; Point Sample Rendering; Rendering Systems; Spatial Data Structures},
pages = {137-146},
title = {{The} randomized sample tree: {A} data structure for interactive walkthroughs in externally stored virtual environments},
venue = {Hong Kong},
year = {2002}
}
@book{faucris.120954284,
address = {Wiesbaden},
author = {Wanka, Rolf},
doi = {10.1007/978-3-8351-9067-2},
faupublication = {yes},
isbn = {978-3-519-00444-8},
note = {UnivIS-Import:2015-04-02:Pub.2006.tech.IMMD.infalg._appro},
publisher = {Teubner},
series = {Leitfäden der Informatik},
title = {{Approximationsalgorithmen} - {Eine} {Einführung}},
year = {2006}
}
@misc{faucris.123498144,
abstract = {Particle Swarm Optimization (PSO) is a nature-inspired meta-heuristic for solving continuous optimization problems. In the literature, the potential of the particles of swarm has been used to show that slightly modified PSO guarantees convergence to local optima. Here we show that under specific circumstances the unmodified PSO, even with swarm parameters known (from the literature) to be good, almost surely does not yield convergence to a local optimum is provided. This undesirable phenomenon is called stagnation. For this purpose, the particles' potential in each dimension is analyzed mathematically. Additionally, some reasonable assumptions on the behavior if the particles' potential are made. Depending on the objective function and, interestingly, the number of particles, the potential in some dimensions may decrease much faster than in other dimensions. Therefore, these dimensions lose relevance, i.e., the contribution of their entries to the decisions about attractor updates becomes insignificant and, with positive probability, they never regain relevance. If Brownian Motion is assumed to be an approximation of the time-dependent drop of potential, practical, i.e., large values for this probability are calculated. Finally, on chosen multidimensional polynomials of degree two, experiments are provided showing that the required circumstances occur quite frequently. Furthermore, experiments are provided showing that even when the very simple sphere function is processed the described stagnation phenomenon occurs. Consequently, unmodified PSO does not converge to any local optimum of the chosen functions for tested parameter settings.},
author = {Raß, Alexander and Schmitt, Manuel and Wanka, Rolf},
faupublication = {yes},
keywords = {Particle swarm optimization; stagnation; potential},
peerreviewed = {automatic},
title = {{Explanation} of {Stagnation} at {Points} that are not {Local} {Optima} in {Particle} {Swarm} {Optimization} by {Potential} {Analysis} [{Extended} {Version}]},
url = {https://arxiv.org/abs/1504.08241},
year = {2015}
}
@inproceedings{faucris.118255544,
abstract = {In this paper, particle trajectories of PSO algorithms in the first iteration are studied. We will prove that many particles leave the search space at the beginning of the optimization process when solving problems with boundary constraints in high-dimensional search spaces. Three different velocity initialization strategies will be investigated, but even initializing velocities to zero cannot prevent this particle swarm explosion. The theoretical analysis gives valuable insight into PSO in high-dimensional bounded spaces, and highlights the importance of bound handling for PSO: As many particles leave the search space in the beginning, bound handling strongly influences particle swarm behavior. Experimental investigations confirm the theoretical results. © 2008 Springer-Verlag Berlin Heidelberg.},
address = {Berlin, Heidelberg},
author = {Helwig, Sabine and Wanka, Rolf},
booktitle = {Proceedings of the 10th International Conference on Parallel Problem Solving from Nature},
date = {2008-09-13/2008-09-17},
doi = {10.1007/978-3-540-87700-4_88},
faupublication = {yes},
note = {UnivIS-Import:2015-04-16:Pub.2008.tech.IMMD.infalg._theor},
pages = {889-898},
publisher = {Springer-verlag},
series = {Lecture Notes in Computer Science (LNCS)},
title = {{Theoretical} {Analysis} of {Initial} {Particle} {Swarm} {Behavior}},
url = {http://www12.informatik.uni-erlangen.de/people/helwig/publications/HW08.php},
venue = {Dortmund},
year = {2008}
}