68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Refine
Year of publication
Document Type
- ZIB-Report (46)
- Master's Thesis (6)
- Software (4)
- Article (1)
- Bachelor's Thesis (1)
Keywords
- Ubiquity Generator Framework (3)
- Computational Diagnosis (2)
- Convex Optimization (2)
- Discrete optimization (2)
- Knee Osteoarthritis (2)
- Lattice problem (2)
- Lattice-based cryptography (2)
- MSM (2)
- Machine Learning (2)
- Parallel algorithms (2)
- Reversible Markov Chain (2)
- Shortest vector problem (2)
- branch-and-bound parallelization (2)
- integer optimization (2)
- parallelization framework (2)
- 2-photon microscopy (1)
- ADOL-C (1)
- Adaptive Importance Sampling (1)
- Automatic differentiation (1)
- Bayesian inverse problem (1)
- Branch and Bound (1)
- Branchwidth (1)
- Carvingwidth (1)
- Classification (1)
- Clinch number (1)
- Combinatorial Optimization, Robust Optimization, Multiband Robustness, Network Design (1)
- Combinatorial optimization (1)
- Computational graph (1)
- Connected Component Labeling (1)
- DVR (1)
- Data Mining (1)
- Data Uncertainty (1)
- Dynamic Traffic (1)
- Elimination number (1)
- Forschungsdatenmanagement (1)
- GPGPU (1)
- GPU acceleration (1)
- Gaussian mixture model (1)
- Generalized Hermite interpolation (1)
- Girsanov (1)
- Harvest Scheduling (1)
- Heterogeneous Wireless Networks, Biobjective Optimization, Mixed Integer Linear Programming, Simulation (1)
- Integer programming (1)
- Ising Model (1)
- Langzeitverfügbarkeit (1)
- Lipschitz continuity (1)
- MINLP (1)
- MIP (1)
- MIPLIB (1)
- Metadynamics (1)
- Metastability (1)
- Mixed Integer Programming (1)
- Mixed Integer Programming, Parallel processing, Node merging, Racing, ParaSCIP, Ubiquity Generator Framework, MIPLIB (1)
- Molecular Dynamics (1)
- Monte Carlo methods for light transport (1)
- Multiband Robustness (1)
- Multiperiod Network Design, Traffic Uncertainty, Robust Optimization, Multiband Robustness, Hybrid Heuristics (1)
- NBLAST (1)
- Network Design (1)
- Network Design, Demand Uncertainty, Robust Optimization, Telecommunications (1)
- Node merging (1)
- Non Equilibrium Sampling (1)
- Optical access networks (1)
- Optimization (1)
- PIPS-SBB, UG, Parallel Branch and Bound (1)
- Parallel Branch-and-Bound (1)
- Parallel processing (1)
- Parallelization, Branch-and-bound, Mixed Integer Programming, UG, ParaSCIP, FiberSCIP, ParaXpress, FiberXpress, SCIP-Jack (1)
- Parameterized complexity (1)
- Periodic Event Scheduling Problem (1)
- Periodic timetabling (1)
- QAP (1)
- Racing ParaSCIP (1)
- Robust Optimization (1)
- Robust Optimization, Uncertainty Set, Multiband Robustness, Network Design (1)
- Round-robin tournament (1)
- SCIP (1)
- Scheduling, Extended Formulations, Network Migration, WDM Networks (1)
- Sports league (1)
- Steiner trees (1)
- Swendsen-Wang Multi-Cluster Algorithm (1)
- Telecommunication (1)
- Tiebreaking criteria (1)
- Time Series (1)
- Treewidth (1)
- Variance Reduction (1)
- Xeon Phi (1)
- acyclic orientations (1)
- algorithm (1)
- bipolar orientations (1)
- boundary conditions (1)
- brain wiring (1)
- branch-and-bound (1)
- cell type (1)
- chromophore concentration (1)
- clustering (1)
- competitive analysis (1)
- constraint integer programming (1)
- coordinate search (1)
- deterministic parallelism (1)
- dht (1)
- digitally reconstructed radiographs (1)
- direct volume rendering (1)
- electron tomography (1)
- enumeration algorithm (1)
- filopodia (1)
- geometric morphometrics (1)
- geometric statistics (1)
- geometry reconstruction (1)
- growth cone dynamics (1)
- image analysis (1)
- image and geometry alignment (1)
- image registration (1)
- importance sampling (1)
- level of detail (1)
- mesh deformation (1)
- metadynamics (1)
- metastability (1)
- microtubules (1)
- mixed integer nonlinear programming (1)
- mixed integer programming (1)
- model (1)
- model-based inversion (1)
- multiple sources and sinks (1)
- natural scene (1)
- neural networks (1)
- neuroinformatics (1)
- neuron similarity (1)
- online algorithms (1)
- online algorithms, stochastic dominance, algorithm analysis, Markov chains (1)
- oxygen saturation (1)
- parallel (1)
- peer-to-peer, machine learning, approximate, clustering, quantile, linear regression (1)
- photoacoustic imaging (1)
- picking (1)
- point correspondence (1)
- pointing (1)
- posterior consistency (1)
- probabilistic analysis (1)
- probabilistic numerics (1)
- quantitative photoacoustic tomography (1)
- random likelihood (1)
- randomised misfit (1)
- rare event simulation (1)
- rendering (1)
- scalaris (1)
- serial sectioning (1)
- shape analysis (1)
- software information, software citation, mathematical research data (1)
- statistical shape and intensity models (1)
- stochastic optimal control (1)
- surrogate model (1)
- survey (1)
- uncertainty quantification (1)
- unfolding, papyri, computed tomography (1)
- volume rendering (1)
Institute
- Mathematical Optimization (23)
- Visual and Data-centric Computing (14)
- Visual Data Analysis (11)
- Applied Algorithmic Intelligence Methods (7)
- Mathematics of Telecommunication (7)
- Numerical Mathematics (5)
- Distributed Algorithms and Supercomputing (4)
- Mathematical Optimization Methods (3)
- Computational Molecular Design (2)
- Digital Data and Information for Society, Science, and Culture (2)
Simulations of the critical Ising model by means of local update algorithms suffer from critical slowing down. One way to partially compensate for the influence of this phenomenon on the runtime of simulations is using increasingly faster and parallel computer hardware. Another approach is using algorithms that do not suffer
from critical slowing down, such as cluster algorithms. This paper reports on the Swendsen-Wang multi-cluster algorithm on Intel Xeon Phi coprocessor 5110P, Nvidia Tesla M2090 GPU, and x86
multi-core CPU. We present shared memory versions of the said algorithm for the simulation of the two- and three-dimensional Ising model. We use a combination of local cluster search and global label reduction by means of atomic hardware primitives. Further, we
describe an MPI version of the algorithm on Xeon Phi and CPU, respectively. Significant performance improvements over known im
plementations of the Swendsen-Wang algorithm are demonstrated.
Heutzutage ist eine Vielzahl der mehrstöckigen Gebäude mit Personenaufzugsgruppen
ausgestattet. Uns wohl bekannt sind die sogenannten konventionellen Systeme. Bei
diesen Systemen betätigt jeder ankommende Passagier eine der beiden Richtungstasten
und teilt dem dahinterstehenden Steuerungsalgorithmus seine gewünschte Startetage
und Fahrtrichtung mit. Betreten wird der zuerst auf der Startetage ankommende Aufzug
mit gleicher Fahrtrichtung und ausreichend Kapazität. Die entsprechende Zieletage
wird dem System erst nach dem Betreten der Fahrgastkabine mitgeteilt. Neben diesen
konventionellen Systemen gibt es Aufzugsgruppen mit Zielrufsteuerung. Die Besonderheit
eines zielrufgesteuerten Systems ist, dass ein ankommender Passagier bereits auf
der Startetage seine gewünschte Zieletage angibt und eine Rückmeldung vom System
erhält, welchen Aufzug er nutzen soll. Diese Zuweisung durch das System hat das Ziel,
die Warte- und Reisezeiten der Passagiere zu minimieren. Ein wesentlicher Faktor bei
der Berechnung warte- und reisezeitminimaler Fahrpläne ist das momentane Verkehrsmuster.
Eine Einteilung der Verkehrsszenarien lässt sich am besten bei Bürogebäuden
vornehmen. So ist es typisch für die Morgenstunden, dass jeder Passagier auf einer
Zugangsebene seine Fahrt beginnt und alle Passagiere die gleiche Fahrtrichtung haben.
Unter einer Zugangsebene ist z. B. der Haupteingang oder ein Parkdeck zu verstehen.
Ein weiterer wesentlicher Punkt bei Zielrufsystemen ist die Art der Zuweisung der Passagiere
durch das System. Zum einen gibt es unmittelbar zuweisende (UZ-) Systeme.
In einem UZ-System wird nach jeder Ankunft eines Passagiers eine Momentaufnahme
des momentanen Verkehrs erstellt und es findet eine Neuplanung und Zuweisung statt.
Eine solche Momentaufnahme werden wir im späteren Verkauf als Schnappschussproblem
bezeichnen. Jeder Passagier bekommt im Anschluss an die Lösung des Schnappschussproblems
eine Mitteilung vom System, z. B. über ein Display, welchen Aufzug
er benutzen soll. Zum anderen gibt es verzögert zuweisende (VZ-) Systeme. In diesen
Systemen wird die Erstellung und Lösung eines Schnappschussproblems bis kurz vor
Ankunft eines Aufzuges auf einer Etage verzögert. In einem VZ-System teilt das System
allen wartenden Passagieren die geplanten Zieletagen des ankommenden Aufzugs mit.
Jeder Passagier, der einen Ruf getätigt hat und zu einer dieser Zieletagen fahren will,
kann jetzt diesen Aufzug betreten. Durch die Verzögerung muss im Vergleich zu einem
UZ-System eine weitaus größere Menge von Passagieren zugewiesen werden. Dadurch
kann der Lösungsprozess bedeutend aufwändiger werden. Vorteil eines VZ-Systems ist
hingegen der größere Freiheitsgrad bei der Optimierung, da aufgrund der späten Zuweisung
die weitere Verkehrsentwicklung mit einbezogen werden kann.
VZ-Systeme sind aufgrund des größeren Freiheitsgrades interessant für die
Praxis ist, wir uns demzufolge in dieser Arbeit mit einer effizienteren Lösung dieser
Art von Schnappschussproblemen befassen. Es genügt dabei den Lösungsprozess eines
Schnappschussproblems zu betrachten. Das Ziel ist eine Reduzierung der benötigten
Rechenzeit. Unter Reoptimierung verstehen wir die Konstruktion
zulässiger Spalten in den jeweiligen Iterationsrunden der Spaltengenerierung
innerhalb eines Schnappschussproblems. Als eine Iterationsrunde bezeichnet wir einer
Menge zulässiger Touren mit negativen reduzierten Kosten. Eine effiziente Reoptimierung
zeichnet sich durch die Wiederverwendung und Aufbereitung von Informationen
aus vorangegangenen Iterationsrunden desselben Schnappschussproblems aus. Zu den
wichtigen Informationen gehört der konstruierte Suchbaum der vorherigen Iterationsrunde
mit seinen ausgeloteten (abgeschnittenen) Blättern sowie konstruierten Touren
bzw. Spalten, welche in der Iterationsrunde ihrer Konstruktion nicht zur Lösung des
Teilproblems der Spaltengenerierung beitrugen. Eine solche Wiederverwendung und
Aufbereitung von Informationen nennen wir Warmstart.
This paper proposes a new method for probabilistic analysis of online algorithms. It is based on the notion of stochastic dominance. We develop the method for
the online bin coloring problem introduced by Krumke et al (2008). Using methods for the stochastic
comparison of Markov chains we establish the result that the performance of the online algorithm GreedyFit is stochastically better than the performance of the algorithm OneBin for any number of items processed. This result gives a more realistic
picture than competitive analysis and explains the behavior observed in simulations.
In this paper we assess to which extent trenching costs of an FTTx network are unavoidable, even if technical side constraints are neglected. For that purpose we present an extended Steiner tree model. Using a variety of realistic problem instances we demonstrate that the total trenching cost can only be reduced by about 5 percent in realistic scenarios. This work has been funded by BMBF (German Federal Ministry of Education and Research) within the program "KMU-innovativ".
In the last 20 years competitive analysis has become the main tool for
analyzing the quality of online algorithms. Despite of this,
competitive analysis has also been criticized: It sometimes cannot
discriminate between algorithms that exhibit significantly different
empirical behavior, or it even favors an algorithm that is worse from
an empirical point of view. Therefore, there have been several
approaches to circumvent these drawbacks. In this survey, we discuss
probabilistic alternatives for competitive analysis.
Radiologists from all application areas are trained to read slice-based visualizations of 3D medical image data. Despite the numerous
examples of sophisticated three-dimensional renderings, especially all variants of direct volume rendering, such methods are
often considered not very useful by radiologists who prefer slice-based visualization. Just recently there have been attempts to bridge this
gap between 2D and 3D renderings. These attempts include specialized techniques for volume picking that result in repositioning slices.
In this paper, we present a new volume picking technique that, in contrast to previous work, does not require pre-segmented data or metadata. The positions picked by our method are solely based on the data itself, the transfer function and,
most importantly, on the way the volumetric rendering is perceived by viewers. To demonstrate the usefulness of the proposed method
we apply it for automatically
repositioning slices in an abdominal MRI
scan, a data set from a flow simulation and a number of other volumetric scalar fields. Furthermore we discuss how the method can be implemented in combination with various different volumetric rendering techniques.
We present a level of detail method for trees based on ellipsoids and lines. We leverage the Expectation Maximization algorithm with a Gaussian Mixture Model to create a hierarchy of high-quality leaf clusterings, while the branches are simplified using agglomerative bottom-up clustering to preserve the connectivity. The simplification runs in a preprocessing step and requires no human interaction. For a fly by over and through a scene of 10k trees, our method renders on average at 40 ms/frame, up to 6 times faster than billboard clouds with comparable artifacts.