Search

In this paper, we study the nurse rostering problem that considers multiple units and many soft time-related constraints. An efficient branch and price solution approach that relies on a fast algorithm to solve the pricing subproblem of the column generation process is presented. For the nurse rostering problem, its pricing subproblem can be formulated as a shortest path problem with resource constraints, which has been the backbone of several solutions for several classical problems like vehicle routing problems. However, approaches that perform well on these problems cannot be used since most constraints in the nurse rostering problem are soft. Based on ideas borrowed from global constraints in constraint programming to model rostering problems, an efficient dynamic programming algorithm with novel label definitions and dominating rules specific to soft time-related constraints is proposed. In addition, several acceleration strategies are employed to improve the branch and price algorithm. Computational results on instances of different sizes indicate that the proposed algorithm is a promising solution for the nurse rostering problem with multiple units.

In the paper "Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares", TCS Volume 769 (2019), pages 63--74, the LHIT problem is proposed as follows: For a given set of non-intersecting line segments ${\cal L} = \{\ell_1, \ell_2, \ldots, \ell_n\}$ in $I\!\!R^2$, compute two axis-parallel congruent squares ${\cal S}_1$ and ${\cal S}_2$ of minimum size whose union hits all the line segments in $\cal L$, and a linear time algorithm was proposed. Later it was observed that the algorithm has a bug. In this corrigendum, we corrected the algorithm. The time complexity of the corrected algorithm is $O(n^2)$.

Persistence diagrams are important tools in the field of topological data analysis that describe the presence and magnitude of features in a filtered topological space. However, current approaches for comparing a persistence diagram to a set of other persistence diagrams is linear in the number of diagrams or do not offer performance guarantees. In this paper, we apply concepts from locality-sensitive hashing to support approximate nearest neighbor search in the space of persistence diagrams. Given a set $\Gamma$ of $n$ $(M,m)$-bounded persistence diagrams, each with at most $m$ points, we snap-round the points of each diagram to points on a cubical lattice and produce a key for each possible snap-rounding. Specifically, we fix a grid over each diagram at several resolutions and consider the snap-roundings of each diagram to the four nearest lattice points. Then, we propose a data structure with $\tau$ levels $\mathbb{D}_{\tau}$ that stores all snap-roundings of each persistence diagram in $\Gamma$ at each resolution. This data structure has size $O(n5^m\tau)$ to account for varying lattice resolutions as well as snap-roundings and the deletion of points with low persistence. To search for a persistence diagram, we compute a key for a query diagram by snapping each point to a lattice and deleting points of low persistence. Furthermore, as the lattice parameter decreases, searching our data structure yields a six-approximation of the nearest diagram in $\Gamma$ in $O((m\log{n}+m^2)\log\tau)$ time and a constant factor approximation of the $k$th nearest diagram in $O((m\log{n}+m^2+k)\log\tau)$ time.

We present measurements of the orientation $\theta_0$ and temperature amplitude $\delta$ of the large-scale circulation in a cylindrical sample of turbulent Rayleigh-Benard convection (RBC) with aspect ratio $\Gamma \equiv D/L = 1.00$ ($D$ and $L$ are the diameter and height respectively) and for the Prandtl number $Pr \simeq 0.8$. Results for $\theta_0$ revealed a preferred orientation with upflow in the West, consistent with a broken azimuthal invariance due to Earth's Coriolis force [see \cite{BA06b}]. They yielded the azimuthal diffusivity $D_\theta$ and a corresponding Reynolds number $Re_{\theta}$ for Rayleigh numbers over the range $2\times 10^{12} < Ra < 1.5\times 10^{14}$. In the classical state ($Ra < 2\times 10^{13}$) the results were consistent with the measurements by \cite{BA06a} for $Ra < 10^{11}$ and $Pr = 4.38$ which gave $Re_{\theta} \propto Ra^{0.28}$, and with the Prandtl-number dependence $Re_{\theta} \propto Pr^{-1.2}$ as found previously also for the velocity-fluctuation Reynolds number $Re_V$ \cite[]{HGBA15b}. At larger $Ra$ the data for $Re_{\theta}(Ra)$ revealed a transition to a new state, known as the "ultimate" state, which was first seen in the Nusselt number $Nu(Ra)$ and in $Re_V(Ra)$ at $Ra^*_1 \simeq 2\times 10^{13}$ and $Ra^*_2 \simeq 8\times 10^{13}$. In the ultimate state we found $Re_{\theta} \propto Ra^{0.40\pm 0.03}$. Recently \cite{SU15} claimed that non-Oberbeck-Boussinesq effects on the Nusselt and Reynolds numbers of turbulent RBC may have been interpreted erroneously as a transition to a new state. We demonstrate that their reasoning is incorrect and that the transition observed in the G\"ottingen experiments and discussed in the present paper is indeed to a new state of RBC referred to as "ultimate"., Comment: 12 pages, 4 figures, to be pub. in JFMR

We report measurements of the temperature variance $\sigma^2(z,r)$ and frequency power spectrum $P(f,z,r)$ ($z$ is the distance from the sample bottom and $r$ the radial coordinate) in turbulent Rayleigh-B\'enard convection (RBC) for Rayleigh numbers $\textrm{Ra} = 1.6\times10^{13}$ and $1.1\times10^{15}$ and for a Prandtl number $\textrm{Pr} \simeq 0.8$ for a sample with a height $L = 224$ cm and aspect ratio $D/L = 0.50$ ($D$ is the diameter). For $z/L$ less than or similar to $0.1$ $\sigma^2(z,r)$ was consistent with a logarithmic dependence on $z$, and there was a universal (independent of $\textrm{Ra}$, $r$, and $z$) normalized spectrum which, for $0.02$ less than or similar to $f\tau_0$ less than or similar to $0.2$, had the form $P(f\tau_0) = P_0 (f\tau_0)^{-1}$ with $P_0 =0.208 \pm 0.008$ a universal constant. Here $\tau_0 = \sqrt{2R}$ where $R$ is the radius of curvature of the temperature autocorrelation function $C(\tau)$ at $\tau = 0$. For $z/L \simeq 0.5$ the measurements yielded $P(f\tau_0) \sim (f\tau_0)^{-\alpha}$ with $\alpha$ in the range from 3/2 to 5/3. All the results are similar to those for velocity fluctuations in shear flows at sufficiently large Reynolds numbers, suggesting the possibility of an analogy between the flows that is yet to be determined in detail., Comment: 5 pages, 4 figures, 1 supplementary material

We report on experimental determinations of the temperature field in the interior (bulk) of turbulent Rayleigh-Benard convection for a cylindrical sample with aspect ratio (diameter over height) of 0.50, both in the classical and in the ultimate state. The Prandtl number was close to 0.8. We find a "logarithmic layer" in which the temperature varies as A*ln(z/L) + B with the distance z from the bottom plate of the sample. The amplitude A varies with radial position r. In the classical state these results are in good agreement with direct numerical simulations (DNS); in the ultimate state there are as yet no DNS. A close analogy between the temperature field in the classical state and the "Law of the Wall" for the time-averaged down-stream velocity in shear flow is discussed., Comment: 27 pages, 15 figures