An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure

We present a fully polynomial time approximation scheme (FPTAS) for a capacitated economic lot-sizing problem with a monotone cost structure. An FPTAS delivers a solution with a given relative error ɛ in time polynomial in the problem size and in 1/ɛ. Such a scheme was developed by van Hoesel and Wagelmans [8] for a capacitated economic lot-sizing problem with monotone concave (convex) production and backlogging cost functions. We omit concavity and convexity restrictions. Furthermore, we take advantage of a straightforward dynamic programming algorithm applied to a rounded problem.     

Recursive functions on the plane and FPTASs for production planning and scheduling problems with two facilities

We consider a production model with two facilities sharing a resource during a time horizon consisting of a number of time periods. Cumulative production levels at the ends of consecutive periods are linked with constraints of a general form. This allows us to give different interpretations related to scheduling and input–output analysis. The model may arise either separately or in the structure of more general production models. In both cases it is reasonable to find an optimal or near-optimal distribution of resources between these two facilities. This helps either to develop a new production plan or to improve an existing one. The problem in question is NP-hard. We show that our approach leads to fully polynomial time approximation schemes (FPTASs).     

Edge states and topological properties of electrons on the bismuth on silicon surface with giant spin-orbit coupling

We derive a model of localized edge states in a finite-width strip for the two-dimensional electron gas formed in the hybrid system of a bismuth monolayer deposited on the silicon interface and described by the nearly free electron model with giant spin-orbit splitting. The edge states have the energy dispersion in the bulk energy gap with a Dirac-like linear dependence on the quasimomentum and the spin polarization coupled to the direction of propagation, demonstrating the properties of a topological insulator. The topological stability of edge states is confirmed by the calculations of the Z ₂ invariant taken from the structure of the Pfaffian for the time reversal operator for the filled bulk bands in the surface Brillouin zone, which is shown to have a stable number of zeros with the variations of material parameters. The proposed properties of the edge states may support future advances in experimental and technological applications of this new material in nanoelectronics and spintronics.     

Correction to: A scaling algorithm for optimizing arbitrary functions over vertices of polytopes

In this paper we present a scaling algorithm for minimizing arbitrary functions over vertices of polytopes in an oracle model of computation which includes an augmentation oracle. For the binary case, when the vertices are 0–1 vectors, we show that the oracle time is polynomial. Also, this algorithm allows us to generalize some concepts of combinatorial optimization concerning performance bounds of greedy algorithms and leads to new bounds for the complexity of the simplex method.

     

Diffusion of particles in a homogeneous pseudofluidized bed

The coefficients of longitudinal and transverse diffusion of the particles in a pseudofluidized bed are calculated for an arbitrary value of the Reynolds number characterizing the flow of the pseudofluidizing medium around the particles. The theory is compared with experiment.Translated from Zhurnal Prikladnoi Mekhaniki i Tekhnicheskoi Fiziki, No. 1, pp. 79–83, January–February, 1972.     

Regular and irregular dynamics of spin-polarized wavepackets in a mesoscopic quantum dot at the edge of topological insulator

The dynamics of Dirac–Weyl spin-polarized wavepackets driven by a periodic electric field is considered for the electrons in a mesoscopic quantum dot formed at the edge of the two-dimensional HgTe/CdTe topological insulator with Dirac–Weyl massless energy spectra, where the motion of carriers is less sensitive to disorder and impurity potentials. It is observed that the interplay of strongly coupled spin and charge degrees of freedom creates the regimes of irregular dynamics in both coordinate and spin channels. The border between the regular and irregular regimes determined by the strength and frequency of the driving field is found analytically within the quasiclassical approach by means of the Ince–Strutt diagram for the Mathieu equation, and is supported by full quantum-mechanical simulations of the driven dynamics. The investigation of quasienergy spectrum by Floquet approach reveals the presence of non-Poissonian level statistics, which indicates the possibility of chaotic quantum dynamics and corresponds to the areas of parameters for irregular regimes within the quasiclassical approach. We find that the influence of weak disorder leads to partial suppression of the dynamical chaos. Our findings are of interest both for progress in the fundamental field of quantum chaotic dynamics and for further experimental and technological applications of spindependent phenomena in nanostructures based on topological insulators.     

A strongly polynomial algorithm for linear systems having a binary solution

This paper proposes a strongly polynomial algorithm which either finds a solution of a linear system Ax?=?b, 0 ≤?x?≤?1, or correctly decides that the system has no 0,1-solutions. The algorithm can be used as the basis for the construction of a polynomial algorithm for linear programming.     

A single-item economic lot-sizing problem with a non-uniform resource: Approximation

We study a generalization of the classical single-item capacitated economic lot-sizing problem to the case of a non-uniform resource usage for production. The general problem and several special cases are shown to be non-approximable with any polynomially computable relative error in polynomial time. An optimal dynamic programming algorithm and its approximate modification are presented for the general problem. Fully polynomial time approximation schemes are developed for two NP-hard special cases: (1) cost functions of total production are separable and holding and backlogging cost functions are linear with polynomially related slopes, and (2) all holding costs are equal to zero.     

TRPM5, a taste-signaling transient receptor potential ion-channel,is a ubiquitous signaling component in chemosensory cells

Background  

A growing number of TRP channels have been identified as key players in the sensation of smell, temperature, mechanical forces and taste. TRPM5 is known to be abundantly expressed in taste receptor cells where it participates in sweet, amino acid and bitter perception. A role of TRPM5 in other sensory systems, however, has not been studied so far.