Simulating optimal structure of the magnetic field of electrostatic plasma lens

The paper considers the motion of electrons in the curvilinear magnetic field of a plasma lens. This motion is modeled mathematically on the assumption that the force acting on the electron is central in a moving coordinate frame. The existence conditions for optimal and stable equipotentials are studied. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 73–78, September–October 2006.     

Convergence of a jump procedure in a semi-Markov environment in diffusion-approximation scheme

The sufficient convergence conditions are obtained for a jump stochastic approximation procedure in a semi-Markov environment in a diffusion approximation scheme with balance conditions for a singular perturbation of the regression function. To this end, a singular perturbation problem is solved for the asymptotic representation of the compensating operator of an augmented Markov renewal process. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 124–133, November–December 2007.     

Ionization of hydrogen molecular ions in an intense laser field via a resonant state

We present a time-dependent Schrödinger equation method in the prolate spheroidal coordinates to study the double ionization of hydrogen molecules in an intense laser field. The time propagation of the electronic wave function is performed by a second order split-operator method in the energy representation. With an adiabatic approximation, we obtain the kinetic energy release (KER) spectra by folding the vibrational wave packet of nuclei with the calculated ionization rates. Our results are in reasonable agreement with the experimental measurement. Furthermore, by including or excluding an individual state in the calculation, we identify that the observed KER peak comes from the ionization of the hydrogen molecular ions via the three-photon resonance of the 2pσu state.     

Continuous stochastic approximation with semi-Markov switchings in the diffusion approximation scheme

The sufficient conditions of convergence are obtained for a continuous stochastic approximation procedure in the diffusion approximation scheme under balance conditions imposed on singular perturbations of the regression function in a semi-Markov environment. To this end, a singular perturbation problem is solved for the asymptotic representation of a compensating operator of a Markov renewal process. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 170–178, July–August 2007.     

Designing Fast Converging Cost Sharing Methods for Multicast Transmissions

We study a multicast game in non-cooperative directed networks in which a source sends the same message or service to a set of r receiving users and the cost of the used links is divided among the receivers according to a given cost sharing method. By following the approach recently proposed by Chen et al. (Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 854–863, 2008), we analyze the performances of a family of methods satisfying certain desiderata, namely, weak and strong budget-balance, fairness and separability. We show that any fair method may require an arbitrary number of selfish moves in order to converge to a pure Nash equilibrium, hence we focus on the solutions obtained after one round of selfish moves. We evaluate their quality according to two global social functions: the overall cost of the solution and the maximum shared cost of users. The only method satisfying all the properties is the well-known Shapley value for which we show an approximation ratio of the solutions reached after a one round walk equal to Θ(r ²). We then prove that relaxing the strong budget balance and separability properties (we call feasible any method satisfying weak budget balance and fairness) leads to improved performances since we determine a feasible method achieving an approximation ratio of the solutions reached after a one round walk equal to O(r). This bound is asymptotically optimal since we also show that any method satisfying weak budget balance cannot achieve an approximation ratio of the solutions reached after a one round walk smaller than r. Finally, we prove the NP-hardness of computing the sequence of moves leading to the best possible global performance and extend most of the results to undirected networks.     

Investigation of a one-channel queueing system with an unlimited queue and the markovian anticipatory switching

Acondition of stability on the second approximation is obtained for a pulse system with anticipatory switching based on the diffusive approximation of normalized deviations of solutions of the system from the solution of an averaged system. The theoretical results obtained are used for investigating a one-channel queueing system with an unlimited queue. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 168–173, July–August, 2000.     

Continuous procedure of stochastic approximation with singular perturbation under balance conditions

Sufficient conditions for the convergence of a continuous stochastic approximation procedure are established for the case where the regression function depends on a Markovian environment and has a singular perturbation that satisfies balance conditions. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 133–139, May–June 2006.     

Approximation processes for resolvent operators

We introduce general sequences of linear operators obtained from classical approximation processes which are useful in the approximation of the resolvent operators of the generators of suitable C ₀-semigroups. The main aim is the representation of the resolvent operators in terms of classical approximation operators. Work performed under the auspices of PRIN 2006–07 “Kolmogorov equations” (coordinator G. Da Prato)     

Modeling of prebreakdown stage of gaseous discharge

A mathematical model of electron cascade transfer is presented. It is developed for studying the prebreakdown stage of gaseous discharge based on the kinetic equation for electrons in a self-consistent electromagnetic field. An elastic scattering of electrons, excitation of molecules by electron impact, and impact ionization are taken into account. A natural ionization background is used as the initial distribution of free electrons. The results of the computational experiment are compared to the data of measurements of drift velocity and the average energy of electrons of discharge, as well as the Townsend coefficient in a flat charged condensor filled with diluted xenon. The comparison showed that the model is not in contrast with the experiment. In order to contract the volume of the discharge’s full current calculation, a transport approximation is built. It is based on the averaging of angular scattering. The applicability of the transport approximation for modeling the full current of the capillary discharge is studied.     

Spectrum Emitted by a Trapped Electron

We study the behaviour of a homonuclear molecule driven by an intense laser field. Newton’s laws are used to describe the dynamics of nuclei while the quantal approach is reserved to the study of the electron. It is observed that the nuclei can oscillate or dissociate according to the degree of ionization of the molecule. In case of low ionization rate it is shown that great amount of information can be obtained by using the simplified approaches of fixed nuclei and of two-state approximation. Under suitable conditions the electron wave function spends a long time localized around one nucleus. The harmonic generation of the molecule is studied and seen to contain even harmonics.     

Efficient MFS Algorithms for Inhomogeneous Polyharmonic Problems

In this work we develop an efficient algorithm for the application of the method of fundamental solutions to inhomogeneous polyharmonic problems, that is problems governed by equations of the form Δ ^ℓ u=f, ℓ∈ℕ, in circular geometries. Following the ideas of Alves and Chen (Adv. Comput. Math. 23:125–142, 2005), the right hand side of the equation in question is approximated by a linear combination of fundamental solutions of the Helmholtz equation. A particular solution of the inhomogeneous equation is then easily obtained from this approximation and the resulting homogeneous problem in the method of particular solutions is subsequently solved using the method of fundamental solutions. The fact that both the problem of approximating the right hand side and the homogeneous boundary value problem are performed in a circular geometry, makes it possible to develop efficient matrix decomposition algorithms with fast Fourier transforms for their solution. The efficacy of the method is demonstrated on several test problems.     

A Sixth-order Image Approximation to the Ionic Solvent Induced Reaction Field

A recent article by Deng and Cai introduced fourth-order image approximations to the reaction field for a charge inside a dielectric sphere immersed in a solvent of low ionic strength (J. Comput. Phys. 227:1246–1266, 2007). To represent such a reaction field, the image approximations employ a point charge at the classical Kelvin image point and two line charges that extend from the Kelvin image point along the radial direction to infinity. In this paper, a sixth-order image approximation is developed, using the same point charge with three different line charges. Procedures on how to discretize the line charges by point image charges and how to implement the resulting point image approximation in O(N) complexity for potential and force field calculations are included. Numerical results demonstrate the sixth-order convergence rate of the image approximation and the O(N) complexity of the fast implementation of the point image approximation.     

Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems

In this paper, we study two variants of the bin packing and covering problems called Maximum Resource Bin Packing (MRBP) and Lazy Bin Covering (LBC) problems, and present new approximation algorithms for them. For the offline MRBP problem, the previous best known approximation ratio is \frac65\frac{6}{5} (=1.2) achieved by the classical First-Fit-Increasing (FFI) algorithm (Boyar et al. in Theor. Comput. Sci. 362(1–3):127–139, 2006). In this paper, we give a new FFI-type algorithm with an approximation ratio of \frac8071\frac{80}{71} (≈1.12676). For the offline LBC problem, it has been shown in Lin et al. (COCOON, pp. 340–349, 2006) that the classical First-Fit-Decreasing (FFD) algorithm achieves an approximation ratio of \frac7160\frac{71}{60} (≈1.18333). In this paper, we present a new FFD-type algorithm with an approximation ratio of \frac1715\frac{17}{15} (≈1.13333). Our algorithms are based on a pattern-based technique and a number of other observations. They run in near linear time (i.e., O(nlog n)), and therefore are practical.     

Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats

Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623–644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494–507, 2002; Tang et al. in J. Comput. Biol. 9:429–446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n ⁵) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002) takes O(n ¹¹) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case. Part of work was done during a Z.-Z. Chen visit at City University of Hong Kong.     

Quantum model and memory of informative biomacromolecules

It is shown, that tubuline informative biomacromolecule has two-well structure potential energy relief for an electron responsible for the switching between conformations of molecules. Therefore the system of conformational excitation in informative biomacromolecules must be described as a two-level quantum system. The energy of the basic electron state ɛ₊ = 1.2 eV and frequency of electron tunneling ω = (6 × 10¹³–6 × 10¹¹) s⁻¹ in a tubuline molecule were calculated. The possibility of data recording by directly collapse of wave function in a two-level cell was shown, thus coherence of quantum state collapses only. The article is published in the original.     

The remainder in the approximation by a generalized Bernstein operator: a representation by a convex combination of second-order divided differences

We investigate the remainder of the approximation formula of a function f∈C[0,1] by means of a generalized Bernstein operator (1.3), depending on two nonnegative integer parameters, introduced by the author in 1984 in the paper [11]. The remainder is expressed in (2.1)–(2.2) by a formula generalizing the author's earlier representation (1.2) of the remainder in Bernstein's classical approximation formula. In (2.13)–(2.14) an expression is given for the remainder involving a linear functional (2.14) which is a convex combination of second-order divided differences. Received: March 1996 / Accepted: April 1996     

Convergence of a modified algorithm of fast probabilistic modeling

The convergence of fast probabilistic modeling algorithms (G-algorithms) is analyzed. A G-algorithm is modified based on a new probabilistic approach, used to reject points in the neighborhood of the current solution. A theoretically justified estimate of the rate of convergence, independent of the initial approximation, is obtained for this modification. A computational experiment is conducted to compare the performance of the modified G-algorithm with that of the classical one. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 173–179, January–February 2008.     

Approximation Algorithms for 3D Orthogonal Knapsack

We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is either forbidden or permitted, and we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms for the non-rotational scenario with approximation ratios 9 ε and 8 ε , as well as an algorithm with approximation ratio 7 ε that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Furthermore, we show how the used techniques can be adapted to the case where rotation by 90° either around the z-axis or around all axes is permitted, where we obtain algorithms with approximation ratios 6 ε and 5 ε , respectively. Finally our methods yield a 3D generalization of a packability criterion and a strip packing algorithm with absolute approximation ratio 29/4, improving the previously best known result of 45/4.     

A Fourth Order Hermitian Box-Scheme with Fast Solver for the Poisson Problem in a Square

A new fourth order box-scheme for the Poisson problem in a square with Dirichlet boundary conditions is introduced, extending the approach in Croisille (Computing 78:329–353, 2006). The design is based on a “hermitian box” approach, combining the approximation of the gradient by the fourth order hermitian derivative, with a conservative discrete formulation on boxes of length 2h. The goal is twofold: first to show that fourth order accuracy is obtained both for the unknown and the gradient; second, to describe a fast direct algorithm, based on the Sherman-Morrison formula and the Fast Sine Transform. Several numerical results in a square are given, indicating an asymptotic O(N ²log ₂(N)) computing complexity.     

Non-approximability of just-in-time scheduling

We consider the following single machine just-in-time scheduling problem with earliness and tardiness costs: Given n jobs with processing times, due dates and job weights, the task is to schedule these jobs without preemption on a single machine such that the total weighted discrepancy from the given due dates is minimum. NP-hardness of this problem is well established, but no approximation results are known. Using the gap-technique, we show in this paper that the weighted earliness–tardiness scheduling problem and several variants are extremely hard to approximate: If n denotes the number of jobs and b∈ℕ is any given constant, then no polynomial-time algorithm can achieve an approximation which is guaranteed to be at most a factor of O(b ⁿ ) worse than the optimal solution unless P = NP.