TY - GEN A1 - Brandt, Andreas A1 - Brandt, Manfred T1 - Workload and busy period for M/GI/1 with a general impatience mechanism N2 - The paper deals with the workload and busy period for the M/GI/1 system under FCFS discipline, where the customers may become impatient during their waiting for service with generally distributed maximal waiting times and also during their service with generally distributed maximal service times depending on the time waited for service. This general impatience mechanism, originally introduced by Kovalenko (1961) and considered by Daley (1965), too, covers the special cases of impatience on waiting times as well as impatience on sojourn times, for which Boxma et al. (2010), (2011) gave new results and outlined special cases recently. Our unified approach bases on the vector process of workload and busy time. Explicit representations for the LSTs of workload and busy period are given in case of phase-type distributed impatience. T3 - ZIB-Report - 11-43 KW - impatient customers KW - workload KW - busy period KW - waiting time dependent service Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14304 SN - 1438-0064 ER - TY - GEN A1 - Manfred, Brandt A1 - Andreas, Brandt T1 - On sojourn times for an infinite-server system in random environment and its application to processor sharing systems N2 - We deal with an infinite-server system where the service speed is governed by a stationary and ergodic process with countably many states. Applying a random time transformation such that the service speed becomes one, the sojourn time of a class of virtual requests with given required service time is equal in distribution to an additive functional defined via a stationary version of the time-changed process. Thus bounds for the expectation of functions of additive functionals yield bounds for the expectation of functions of virtual sojourn times, in particular bounds for fractional moments and the distribution function. Interpreting the $GI(n)/GI(n)/\infty$ system or equivalently the $GI(n)/GI$ system under state-dependent processor sharing as an infinite-server system with random states given by the number $n$ of requests in the system provides results for sojourn times of virtual requests. In case of $M(n)/GI(n)/\infty$, the sojourn times of arriving and added requests are equal in distribution to sojourn times of virtual requests in modified systems, which yields many results for the sojourn times of arriving and added requests. In case of integer moments, the bounds generalize earlier results for $M/GI(n)/\infty$. In particular, the mean sojourn times of arriving and added requests in $M(n)/GI(n)/\infty$ are proportional to the required service time, generalizing Cohen's famous result for $M/GI(n)/\infty$. T3 - ZIB-Report - 11-28 KW - infinite-server KW - random environment KW - time transformation KW - sojourn times KW - state-dependent processor sharing Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-13190 ER - TY - GEN A1 - Heinz, Stefan A1 - Beck, J. Christopher T1 - Reconsidering Mixed Integer Programming and MIP-based Hybrids for Scheduling N2 - Despite the success of constraint programming (CP) for scheduling, the much wider penetration of mixed integer programming (MIP) technology into business applications means that many practical scheduling problems are being addressed with MIP, at least as an initial approach. Furthermore, there has been impressive and well-documented improvements in the power of generic MIP solvers over the past decade. We empirically demonstrate that on an existing set of resource allocation and scheduling problems standard MIP and CP models are now competitive with the state-of-the-art manual decomposition approach. Motivated by this result, we formulate two tightly coupled hybrid models based on constraint integer programming (CIP) and demonstrate that these models, which embody advances in CP and MIP, are able to out-perform the CP, MIP, and decomposition models. We conclude that both MIP and CIP are technologies that should be considered along with CP for solving scheduling problems. T3 - ZIB-Report - 12-05 KW - constraint integer programming KW - constraint programming KW - cumulative constraint KW - mixed integer programming KW - optional activities Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14660 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Vredeveld, Tjark T1 - Stochastic dominance analysis of Online Bin Coloring algorithms N2 - 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. T3 - ZIB-Report - 12-42 KW - online algorithms, stochastic dominance, algorithm analysis, Markov chains Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16502 SN - 1438-0064 ER - TY - GEN A1 - Weber, Britta A1 - Tranfield, Erin M. A1 - Höög, Johanna L. A1 - Baum, Daniel A1 - Antony, Claude A1 - Hyman, Tony A1 - Verbavatz, Jean-Marc A1 - Prohaska, Steffen T1 - Automated stitching of microtubule centerlines across serial electron tomograms N2 - Tracing microtubule centerlines in serial section electron tomography requires microtubules to be stitched across sections, that is lines from different sections need to be aligned, endpoints need to be matched at section boundaries to establish a correspondence between neighboring sections, and corresponding lines need to be connected across multiple sections. We present computational methods for these tasks: 1) An initial alignment is computed using a distance compatibility graph. 2) A fine alignment is then computed with a probabilistic variant of the iterative closest points algorithm, which we extended to handle the orientation of lines by introducing a periodic random variable to the probabilistic formulation. 3) Endpoint correspondence is established by formulating a matching problem in terms of a Markov random field and computing the best matching with belief propagation. Belief propagation is not generally guaranteed to converge to a minimum. We show how convergence can be achieved, nonetheless, with minimal manual input. In addition to stitching microtubule centerlines, the correspondence is also applied to transform and merge the electron tomograms. We applied the proposed methods to samples from the mitotic spindle in C. elegans, the meiotic spindle in X. laevis, and sub-pellicular microtubule arrays in T. brucei. The methods were able to stitch microtubules across section boundaries in good agreement with experts’ opinions for the spindle samples. Results, however, were not satisfactory for the microtubule arrays. For certain experiments, such as an analysis of the spindle, the proposed methods can replace manual expert tracing and thus enable the analysis of microtubules over long distances with reasonable manual effort. T3 - ZIB-Report - 14-41 KW - electron tomography KW - microtubules KW - serial sectioning KW - image analysis KW - geometry reconstruction KW - image and geometry alignment KW - point correspondence Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52958 SN - 1438-0064 ER - TY - GEN A1 - Weber, Marcus A1 - Quer, Jannes T1 - Estimating exit rates in rare event dynamical systems via extrapolation N2 - In this article we present a new idea for approximating exit rates for diffusion processes living in a craggy landscape. We are especially interested in the exit rates of a process living in a metastable regions. Due to the fact that Monte Carlo simulations perform quite poor and are very computational expensive in this setting we create several similar situations with a smoothed potential. For this we introduce a new parameter $\lambda \in [0,1]$ ($\lambda = 1$ very smoothed potential, $\lambda=0$ original potential) into the potential which controls the influence the smoothing. We then sample the exit rate for different parameters $\lambda$ the exit rate from a given region. Due to the fact that $\lambda$ is connected to the exit rate we can use this dependency to approximate the real exit rate. The method can be seen as something between hyperdynamics and temperature accelerated MC. T3 - ZIB-Report - 15-54 KW - rare event sampling, smoothing, membership functions, perturbed potential Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56622 SN - 1438-0064 ER - TY - GEN A1 - Lie, Han Cheng A1 - Sullivan, T. J. T1 - Cameron--Martin theorems for sequences of Cauchy-distributed random variables N2 - Given a sequence of Cauchy-distributed random variables defined by a sequence of location parameters and a sequence of scale parameters, we consider another sequence of random variables that is obtained by perturbing the location or scale parameter sequences. Using a result of Kakutani on equivalence of infinite product measures, we provide sufficient conditions for the equivalence of laws of the two sequences. T3 - ZIB-Report - 16-40 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60230 SN - 1438-0064 ER - TY - GEN A1 - Sullivan, T. J. T1 - Well-posed Bayesian inverse problems and heavy-tailed stable Banach space priors N2 - This article extends the framework of Bayesian inverse problems in infinite-dimensional parameter spaces, as advocated by Stuart (Acta Numer. 19:451–559, 2010) and others, to the case of a heavy-tailed prior measure in the family of stable distributions, such as an infinite-dimensional Cauchy distribution, for which polynomial moments are infinite or undefined. It is shown that analogues of the Karhunen–Loève expansion for square-integrable random variables can be used to sample such measures. Furthermore, under weaker regularity assumptions than those used to date, the Bayesian posterior measure is shown to depend Lipschitz continuously in the Hellinger metric upon perturbations of the misfit function and observed data. T3 - ZIB-Report - 16-30 KW - Bayesian inverse problems KW - heavy-tailed distribution KW - Karhunen–Loève expansion KW - stable distribution KW - uncertainty quantification KW - well-posedness Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59422 SN - 1438-0064 ER - TY - GEN A1 - Witzig, Jakob A1 - Beckenbach, Isabel A1 - Eifler, Leon A1 - Fackeldey, Konstantin A1 - Gleixner, Ambros A1 - Grever, Andreas A1 - Weber, Marcus T1 - Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes N2 - In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst. T3 - ZIB-Report - 16-39 KW - Non-reversible Markov Processes KW - NESS KW - Mixed-Integer Programming KW - Markov State Models Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60353 SN - 1438-0064 ER - TY - GEN A1 - Quer, Jannes A1 - Lie, Han Cheng T1 - Some connections between importance sampling and enhanced sampling methods in molecular dynamics N2 - Enhanced sampling methods play an important role in molecular dynamics, because they enable the collection of better statistics of rare events that are important in many physical phenomena. We show that many enhanced sampling methods can be viewed as methods for performing importance sampling, by identifying important correspondences between the language of molecular dynamics and the language of probability theory. We illustrate these connections by highlighting the similarities between the rare event simulation method of Hartmann and Schütte (J. Stat. Mech. Theor. Exp., 2012), and the enhanced sampling method of Valsson and Parrinello (Phys. Rev. Lett. 113, 090601). We show that the idea of changing a probability measure is fundamental to both enhanced sampling and importance sampling. T3 - ZIB-Report - 17-30 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64289 SN - 1438-0064 ER -