TY - GEN A1 - Hiller, Benjamin A1 - Vredeveld, Tjark T1 - Probabilistic alternatives for competitive analysis N2 - 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. T3 - ZIB-Report - 11-55 KW - online algorithms KW - probabilistic analysis KW - competitive analysis KW - survey Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15131 SN - 1438-0064 ER - TY - GEN A1 - Griewank, Andreas A1 - Streubel, Tom A1 - Lehmann, Lutz A1 - Hasenfelder, Richard A1 - Radons, Manuel T1 - Piecewise linear secant approximation via Algorithmic Piecewise Differentiation N2 - It is shown how piecewise differentiable functions \(F: R^n → R^m\) that are defined by evaluation programs can be approximated locally by a piecewise linear model based on a pair of sample points x̌ and x̂. We show that the discrepancy between function and model at any point x is of the bilinear order O(||x − x̌|| ||x − x̂||). This is a little surprising since x ∈ R^n may vary over the whole Euclidean space, and we utilize only two function samples F̌ = F(x̌) and F̂ = F(x̂), as well as the intermediates computed during their evaluation. As an application of the piecewise linearization procedure we devise a generalized Newton’s method based on successive piecewise linearization and prove for it sufficient conditions for convergence and convergence rates equaling those of semismooth Newton. We conclude with the derivation of formulas for the numerically stable implementation of the aforedeveloped piecewise linearization methods. T3 - ZIB-Report - 16-54 KW - Automatic differentiation KW - Computational graph KW - Lipschitz continuity KW - Generalized Hermite interpolation KW - ADOL-C Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61642 SN - 1438-0064 ER - TY - GEN A1 - Wiebel, Alexander A1 - Vos, Frans M. A1 - Hege, Hans-Christian T1 - Perception-Oriented Picking of Structures in Direct Volumetric Renderings N2 - 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. T3 - ZIB-Report - 11-45 KW - DVR KW - picking KW - pointing KW - direct volume rendering Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14343 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Reisch, Julian T1 - Parameterized Complexity of Periodic Timetabling N2 - Public transportation networks are typically operated with a periodic timetable. The Periodic Event Scheduling Problem (PESP) is the standard mathematical modelling tool for periodic timetabling. Since PESP can be solved in linear time on trees, it is a natural question to ask whether there are polynomial-time algorithms for input networks of bounded treewidth. We show that deciding the feasibility of a PESP instance is NP-hard even when the treewidth is 2, the branchwidth is 2, or the carvingwidth is 3. Analogous results hold for the optimization of reduced PESP instances, where the feasibility problem is trivial. To complete the picture, we present two pseudo-polynomial-time dynamic programming algorithms solving PESP on input networks with bounded tree- or branchwidth. We further analyze the parameterized complexity of PESP with bounded cyclomatic number, diameter, or vertex cover number. For event-activity networks with a special -- but standard -- structure, we give explicit and sharp bounds on the branchwidth in terms of the maximum degree and the carvingwidth of an underlying line network. Finally, we investigate several parameters on the smallest instance of the benchmarking library PESPlib. T3 - ZIB-Report - 20-15 KW - Parameterized complexity KW - Periodic timetabling KW - Treewidth KW - Branchwidth KW - Carvingwidth KW - Periodic Event Scheduling Problem Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78314 SN - 1438-0064 ER - TY - GEN A1 - Munguia, Lluis-Miquel A1 - Oxberry, Geoffrey A1 - Rajan, Deepak A1 - Shinano, Yuji T1 - Parallel PIPS-SBB: Multi-Level Parallelism For Stochastic Mixed-Integer Programs N2 - PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve MIPs with a dual-block angular structure, which is characteristic of deterministic-equivalent Stochastic Mixed-Integer Programs (SMIPs). In this paper, we present two different parallelizations of Branch & Bound (B&B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator (UG), a universal framework for parallelizing B&B tree search that has been successfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores. T3 - ZIB-Report - 17-58 KW - PIPS-SBB, UG, Parallel Branch and Bound Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65517 SN - 1438-0064 IS - ZIB-Report 17-58 ER - TY - GEN A1 - Bauschert, Thomas A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio A1 - Koster, Arie M.C.A. A1 - Kutschka, Manuel A1 - Steglich, Uwe T1 - Network Planning under Demand Uncertainty with Robust Optimization N2 - The planning of a communication network is inevitably depending on the quality of both the planning tool and the demand forecast used. In this article, we show exemplarily how the emerging area of Robust Optimization can advance the network planning by a more accurate mathematical description of the demand uncertainty. After a general introduction of the concept and its application to a basic network design problem, we present two applications: multi-layer and mixed-line-rate network design. We conclude with a discussion of extensions of the robustness concept to increase the accuracy of handling uncertainties. T3 - ZIB-Report - 13-59 KW - Network Design, Demand Uncertainty, Robust Optimization, Telecommunications Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42557 SN - 1438-0064 ER - TY - GEN A1 - Costa, Marta A1 - Manton, James D. A1 - Ostrovsky, Aaron D. A1 - Prohaska, Steffen A1 - Jefferis, Gregory S.X.E. T1 - NBLAST: Rapid, sensitive comparison of neuronal structure and construction of neuron family databases N2 - Neural circuit mapping is generating datasets of 10,000s of labeled neurons. New computational tools are needed to search and organize these data. We present NBLAST, a sensitive and rapid algorithm, for measuring pairwise neuronal similarity. NBLAST considers both position and local geometry, decomposing neurons into short segments; matched segments are scored using a probabilistic scoring matrix defined by statistics of matches and non-matches. We validated NBLAST on a published dataset of 16,129 single Drosophila neurons. NBLAST can distinguish neuronal types down to the finest level (single identified neurons) without a priori information. Cluster analysis of extensively studied neuronal classes identified new types and unreported topographical features. Fully automated clustering organized the validation dataset into 1052 clusters, many of which map onto previously described neuronal types. NBLAST supports additional query types including searching neurons against transgene expression patterns. Finally we show that NBLAST is effective with data from other invertebrates and zebrafish. T3 - ZIB-Report - 16-34 KW - neuroinformatics KW - NBLAST KW - neuron similarity KW - cell type KW - clustering Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59672 SN - 1438-0064 ER - TY - GEN A1 - D'Andreagiovanni, Fabio A1 - Raymond, Annie T1 - Multiband Robust Optimization and its Adoption in Harvest Scheduling N2 - A central assumption in classical optimization is that all the input data of a problem are exact. However, in many real-world problems, the input data are subject to uncertainty. In such situations, neglecting uncertainty may lead to nominally optimal solutions that are actually suboptimal or even infeasible. Robust optimization offers a remedy for optimization under uncertainty by considering only the subset of solutions protected against the data deviations. In this paper, we provide an overview of the main theoretical results of multiband robustness, a new robust optimization model that extends and refines the classical theory introduced by Bertsimas and Sim. After introducing some new results for the special case of pure binary programs, we focus on the harvest scheduling problem and show how multiband robustness can be adopted to tackle the uncertainty affecting the volume of produced timber and grant a reduction in the price of robustness. T3 - ZIB-Report - 13-76 KW - Data Uncertainty KW - Robust Optimization KW - Multiband Robustness KW - Harvest Scheduling Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-43380 SN - 1438-0064 ER - TY - GEN A1 - Ambellan, Felix A1 - Hanik, Martin A1 - von Tycowicz, Christoph T1 - Morphomatics: Geometric morphometrics in non-Euclidean shape spaces N2 - Morphomatics is an open-source Python library for (statistical) shape analysis developed within the geometric data analysis and processing research group at Zuse Institute Berlin. It contains prototype implementations of intrinsic manifold-based methods that are highly consistent and avoid the influence of unwanted effects such as bias due to arbitrary choices of coordinates. KW - shape analysis KW - geometric statistics KW - geometric morphometrics Y1 - 2021 U6 - https://doi.org/10.12752/8544 N1 - https://morphomatics.github.io/ ER - TY - GEN A1 - Kaplan, Bernhard A1 - Laufer, Jan A1 - Prohaska, Steffen A1 - Buchmann, Jens T1 - Monte-Carlo-based inversion scheme for 3D quantitative photoacoustic tomography N2 - The goal of quantitative photoacoustic tomography (qPAT) is to recover maps of the chromophore distributions from multiwavelength images of the initial pressure. Model-based inversions that incorporate the physical processes underlying the photoacoustic (PA) signal generation represent a promising approach. Monte-Carlo models of the light transport are computationally expensive, but provide accurate fluence distributions predictions, especially in the ballistic and quasi-ballistic regimes. Here, we focus on the inverse problem of 3D qPAT of blood oxygenation and investigate the application of the Monte-Carlo method in a model-based inversion scheme. A forward model of the light transport based on the MCX simulator and acoustic propagation modeled by the k-Wave toolbox was used to generate a PA image data set acquired in a tissue phantom over a planar detection geometry. The combination of the optical and acoustic models is shown to account for limited-view artifacts. In addition, the errors in the fluence due to, for example, partial volume artifacts and absorbers immediately adjacent to the region of interest are investigated. To accomplish large-scale inversions in 3D, the number of degrees of freedom is reduced by applying image segmentation to the initial pressure distribution to extract a limited number of regions with homogeneous optical parameters. The absorber concentration in the tissue phantom was estimated using a coordinate descent parameter search based on the comparison between measured and modeled PA spectra. The estimated relative concentrations using this approach lie within 5 % compared to the known concentrations. Finally, we discuss the feasibility of this approach to recover the blood oxygenation from experimental data. T3 - ZIB-Report - 17-04 KW - quantitative photoacoustic tomography KW - model-based inversion KW - oxygen saturation KW - chromophore concentration KW - photoacoustic imaging KW - Monte Carlo methods for light transport KW - boundary conditions KW - coordinate search Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-62318 SN - 1438-0064 ER -