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) (remove)
Has Fulltext
- yes (46)
Keywords
Institute
- Mathematical Optimization (21)
- Visual Data Analysis (9)
- Visual and Data-centric Computing (9)
- Mathematics of Telecommunication (7)
- Applied Algorithmic Intelligence Methods (6)
- Numerical Mathematics (4)
- Mathematical Optimization Methods (3)
- Digital Data and Information for Society, Science, and Culture (2)
- Distributed Algorithms and Supercomputing (2)
- Image Analysis in Biology and Materials Science (2)
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.
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.
We provide an overview of our main results about studying Linear Programming Problems whose coefficient matrix is subject to uncertainty and the uncertainty is modeled through a multi-band set. Such an uncertainty set generalizes the classical one proposed by Bertsimas and Sim and is particularly suitable in the common case of arbitrary non-symmetric distributions of the parameters. Our investigations were inspired by practical needs of our industrial partner in ongoing projects with focus on the design of robust telecommunications networks.
The rapid technological evolution of telecommunication networks demands service providers to regularly update their technology, with the aim of remaining competitive in the marketplace. However, upgrading the technology in a network is not a trivial task. New hardware components need to be installed in the network and during the installation network connectivity may be temporarily compromised. The Wavelength Division Multiplexing (WDM) technology, whose upgrade is considered in here, shares fiber links among several optical connections and tearing down a single link may disrupt several optical connections at once. When the upgrades involve large parts of a network, typically not all links can be upgraded in parallel, which may lead to an unavoidable longer disruption of some connections. A bad scheduling of the overall endeavor, however, can dramatically increase the disconnection time of parts of the networks, causing extended service disruption. In this contribution, we study the problem of finding a schedule of the fiber link upgrades that minimizes the total service disruption time. To the best of our knowledge, this problem has not yet been formalized and investigated. The aim of our work is to close this gap by presenting a mathematical optimization model for the problem and an innovative solution algorithm that tackles the intrinsic difficulties of the problem. Computational experience on realistic instances completes our study. Our original investigations have been driven by real needs of DFN, operator of the German National Research and Education Network and our partner in the BMBF research project ROBUKOM (http://www.robukom.de/).
We propose a novel optimization model for resource assignment in heterogeneous wireless network. The model adopts two objective functions maximizing the number of served users and the minimum granted utility at once. A distinctive feature of our new model is to consider two consecutive time slots, in order to include handover as an additional decision dimension.
Furthermore, the solution algorithm that we propose refines a heuristic solution approach recently proposed in literature, by considering a real joint optimization of the considered resources. The simulation study shows that the new model leads to a significant reduction in handover frequency, when compared to a traditional scheme based on maximum SNR.
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.