MinT—Architecture and applications of the (t, m, s)-net and OOA database

Many different constructions for (t,m,s)$(t\text{,}m\text{,}s)$-nets and (t,s)$(t\text{,}s)$-sequences are known today. Propagation rules as well as connections to other mathematical objects make it difficult to determine the best net available in a given setting.     

Sampling methods for shortest vectors,closest vectors and successive minima

We study four problems from the geometry of numbers, the shortest vector problem  (Svp)$\left(\text{<small-caps>Svp</small-caps>}\right)$, the closest vector problem  (Cvp)$\left(\text{<small-caps>Cvp</small-caps>}\right)$, the successive minima problem  (Smp)$\left(\text{<small-caps>Smp</small-caps>}\right)$, and the shortest independent vectors problem   (Sivp$\text{<small-caps>Sivp</small-caps>}$). Extending and generalizing results of Ajtai, Kumar, and Sivakumar we present probabilistic single exponential time algorithms for all four problems for all _?p${?}_p$ norms. The results on Smp$\text{<small-caps>Smp</small-caps>}$ and Sivp$\text{<small-caps>Sivp</small-caps>}$ are new for all norms. The results on Svp$\text{<small-caps>Svp</small-caps>}$ and Cvp$\text{<small-caps>Cvp</small-caps>}$ generalize previous results of Ajtai et al. for the Euclidean _?2${?}_2$ norm to arbitrary _?p${?}_p$ norms. We achieve our results by introducing a new lattice problem, the generalized shortest vector problem   (GSvp$\text{<small-caps>GSvp</small-caps>}$). ¹ We describe a single exponential time algorithm for GSvp$\text{<small-caps>GSvp</small-caps>}$. We also describe polynomial time reductions from Svp,Cvp,Smp$\text{<small-caps>Svp</small-caps>},\text{<small-caps>Cvp</small-caps>},\text{<small-caps>Smp</small-caps>}$, and Sivp$\text{<small-caps>Sivp</small-caps>}$ to GSvp$\text{<small-caps>GSvp</small-caps>}$, establishing single exponential time algorithms for the four classical lattice problems. This approach leads to a unified algorithmic treatment of the lattice problems Svp,Cvp,Smp$\text{<small-caps>Svp</small-caps>},\text{<small-caps>Cvp</small-caps>},\text{<small-caps>Smp</small-caps>}$, and Sivp$\text{<small-caps>Sivp</small-caps>}$.     

Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints

In this paper we consider the problem of scheduling n$n$ preemptive jobs on m$m$ machines with identical speed under machine availability and eligibility constraints when minimizing maximum lateness (_Lmax$(L_{\max }$). The lateness of a job is defined to be its completion time minus its due date, and _Lmax$L_{\max }$ is the maximum value of lateness among all jobs. We assume that each machine is not continuously available at all time throughout the planning horizon and each job is only allowed to be processed on specific machines. Network flow technique is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time two-phase binary search algorithm to verify the feasibility of the problem and to solve the scheduling problem optimally if a feasible schedule exists. Finally, we show that the time complexity of the algorithm is O((n+(2n+2x))³log(UB-LB))$O((n+(2n+2x){)}^3\log (\text{<italic>UB</italic>}-\text{<italic>LB</italic>}))$. Most literature in parallel machine scheduling assume that all machines are continuously available for processing and all jobs can be processed at any available machine throughout the planning horizon. But both assumptions might not be true in some practical environment, such as machine preventive maintenance and machines that have different capabilities to process jobs. This type of scheduling problem is seldom studied in the literature. The purpose of this paper is to examine the scheduling problem with machines with identical speed under machine availability and eligibility constraints. The objective is to minimize maximum lateness. We formulate this scheduling problem into a series of maximum flow problems with different values of _Lmax$L_{\max }$. A polynomial time two-phase binary search algorithm is proposed to verify the feasibility of the problem and to determine the optimal _Lmax$L_{\max }$.     

A fast algorithm for solving the space–time fractional diffusion equation

In this paper, we propose a fast algorithm for efficient and accurate solution of the space–time fractional diffusion equations defined in a rectangular domain. The spatial discretization is done by using the central finite difference scheme and matrix transfer technique. Due to its nonlocality, numerical discretization of the spectral fractional Laplacian ${(?\Delta )}_s^{\alpha /2}$ results in a large dense matrix. This causes considerable challenges not only for storing the matrix but also for computing matrix–vector products in practice. By utilizing the compact structure of the discrete system and the discrete sine transform, our algorithm avoids to store the large matrix from discretizing the nonlocal operator and also significantly reduces the computational costs. We then use the Laplace transform method for time integration of the semi-discretized system and a weighted trapezoidal method to numerically compute the convolutions needed in the resulting scheme. Various experiments are presented to demonstrate the efficiency and accuracy of our method.     

Self-deployment of mobile sensors on a ring

Mobile sensors can self-deploy in a purely decentralized and distributed fashion, so as to reach in a finite time a state of static equilibrium in which they uniformly cover the environment. We consider the self-deployment problem in a ring (e.g., a circular rim); in particular we investigate under what conditions the problem is solvable by a collection of identical sensors without a global coordinate system, however capable of determining the location (in their local coordinate system) of the other sensors within a fixed distance (called visibility radius). A self-deployment is exact   if within finite time the distance between any two consecutive sensors along the ring is the same, d$d$; it is ?$?$-approximate   if within finite time the distance between two consecutive sensors is between d−?$d-?$ and d+?$d+?$.     

Langmuir probe RF plasma compensation using a simulation method

The problem of Langmuir probe data deformation due to RF pickup by the probe is treated through a computer simulation method. It is pointed out that proper RF compensations can be obtained by treatment of the Langmuir probe raw data through the use of computer software. It is demonstrated that correct, RF unaffected probe I–V$I\text{–}V$ characteristics can be accurately reproduced from the RF contaminated data. This eliminates the need for the use of any filters or other hardware procedures. User friendly matlab based software is presented. The software automatically retrieves the correct RF I–V$I\text{–}V$ characteristics for single Langmuir probe data which consequently allows for proper evaluation of plasma parameters such as the plasma electron temperature, electron number density and the electron energy distribution function (EEDF)     

Erlang loss queueing system with batch arrivals operating in a random environment

We consider the BMAP/PH/N/0$\text{<italic>BMAP</italic>}/\text{<italic>PH</italic>}/N/0$ queueing system operating in a finite state space Markovian random environment. Disciplines of partial admission, complete rejection and complete admission are analyzed. The stationary distribution of the system states is calculated. The loss probability and other main performance measures of the system are derived. The Laplace–Stieltjes transform of the sojourn time distribution of accepted customers is obtained. Illustrative numerical examples are presented. They show effect of an admission strategy, a correlation in an arrival process, a variation of a service process. Poor quality of the loss probability approximation by means of more simple models utilization is illustrated.     

A stabilized finite volume method for the evolutionary Stokes–Darcy system

In this paper, we propose a stabilized fully discrete finite volume method based on two local Gauss integrals for a non-stationary Stokes–Darcy problem. This stabilized method is free of stabilized parameters and uses the lowest equal-order finite element triples $P1\text{–}P1\text{–}P1$ for approximating the velocity, pressure and hydraulic head of the Stokes–Darcy model. Under a modest time step restriction in relation to physical parameters, we give the stability analysis and the error estimates for the stabilized finite volume scheme by means of a relationship between finite volume and finite element approximations with the lower order elements. Finally, a series of numerical experiments are provided to demonstrate the validity of the theoretical results.     

A genetic algorithm for joint replenishment based on the exact inventory cost

Given the order cycles of items in joint replenishment, no closed-form formula or efficient method is known to compute the exact inventory cost. Previous studies avoid the difficulty by restricting the replenishment policy to the cases where the order cycle of each item is a multiple of the cycle of the most frequently ordered item. This simplifies the computation but may entail sub-optimality of a solution. To cope with this, we devise an unbiased estimator of the exact cost which is computable in time polynomial of the problem input size and 1/ε$1/\epsilon$, where ε$\epsilon$ is a pre-specified relative error of estimation. We then develop a genetic algorithm based on this new cost evaluation, report the experimental results in comparison to the “RAND” [Kaspi M, Rosenblatt MJ. An improvement of Silver's algorithm for the joint replenishment problem. IIE Transactions 1983; 15: 264–9] which has been known as a state-of-the-art method for joint replenishment, and discuss their implications.     

Isotopic triangulation of a real algebraic surface

We present a new algorithm for computing the topology of a real algebraic surface S$S$ in a ball B$B$, even in singular cases. We use algorithms for 2D and 3D algebraic curves and show how one can compute a topological complex equivalent to S$S$, and even a simplicial complex isotopic to S$S$ by exploiting properties of the contour curve of S$S$. The correctness proof of the algorithm is based on results from stratification theory. We construct an explicit Whitney stratification of S$S$, by resultant computation. Using Thom’s isotopy lemma, we show how to deduce the topology of S$S$ from a finite number of characteristic points on the surface. An analysis of the complexity of the algorithm and effectiveness issues conclude the paper.     

On some special solutions to periodic Benjamin-Ono equation with discrete Laplacian

We investigate a periodic version of the Benjamin-Ono (BO) equation associated with a discrete Laplacian. We find some special solutions to this equation, and calculate the values of the first two integrals of motion _I1$I_1$ and _I2$I_2$ corresponding to these solutions. It is found that there exists a strong resemblance between them and the spectra for the Macdonald q$q$-difference operators. To better understand the connection between these classical and quantum integrable systems, we consider the special degenerate case corresponding to q=0$q=0$ in more detail. Namely, we give general solutions to this degenerate periodic BO, obtain explicit formulas representing all the integrals of motions _In$I_n$ (n=1,2,…$n=1\text{,}2\text{,}\dots$), and successfully identify it with the eigenvalues of Macdonald operators in the limit q→0$q\to 0$, i.e. the limit where Macdonald polynomials tend to the Hall–Littlewood polynomials.     

Calculations of distance distributions and probabilities of binding by ligands between parallel plane membranes comprising receptors

Cell communication through biochemical signaling pathways is a key determinant of tissue responses to radiation. Several molecules, such as the transforming growth factor β$\beta$ (TGFβ$\beta$), are implicated in radiation-induced signaling between cells. Brownian Dynamics (BD) algorithms have recently been used to simulate the interaction of ligands with receptors and to elucidate signal transduction and autocrine loops in ligand–receptors systems. In this paper, we discuss the simulation of particle diffusion and binding kinetics in a space bounded by two parallel plane membranes, using an exact algorithm to sample the propagator (Green’s function) of a particle located between 2 membranes. We also show that the simulation results are independent of the number of time steps used, in accordance with time discretization equations. These simulations could be used to simulate the motion and binding of ligand molecules in a cell culture, and possibly in neuronal synapses.