An approximation algorithm for finding a <Emphasis Type="Italic">d</Emphasis>-regular spanning connected subgraph of maximum weight in a complete graph with random weights of edges

An approximation algorithm is suggested for the problem of finding a d-regular spanning connected subgraph of maximum weight in a complete undirected weighted n-vertex graph. Probabilistic analysis of the algorithm is carried out for the problem with random input data (some weights of edges) in the case of a uniform distribution of the weights of edges and in the case of a minorized type distribution. It is shown that the algorithm finds an asymptotically optimal solution with time complexity O(n ²) when d = o(n). For the minimization version of the problem, an additional restriction on the dispersion of weights of the graph edges is added to the condition of the asymptotical optimality of the modified algorithm.     

Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles

We consider the m-Cycle Cover Problem of covering a complete undirected graph by m vertex-nonadjacent cycles of extremal total edge weight. The so-called TSP approach to the construction of an approximation algorithm for this problem with the use of a solution of the traveling salesman problem (TSP) is presented. Modifications of the algorithm for the Euclidean Max m-Cycle Cover Problem with deterministic instances (edge weights) in a multidimensional Euclidean space and the Random Min m-Cycle Cover Problem with random instances UNI(0,1) are analyzed. It is shown that both algorithms have time complexity O(n ³) and are asymptotically optimal for the number of covering cycles m = o(n) and \(m \leqslant \frac{{n^{1/3} }}{{\ln n}}\), respectively.     

Estimate of solution stability in a two-dimensional inverse problem for elasticity equations

The problem of determining the density of the medium and one of its elasticity moduli is considered. Properties of the elastic medium and external forces are assumed to be independent of the coordinate x ₃. In this case, the third component of the displacement vector satisfies a scalar equation of the second order, which contains the density ρ of the medium and elasticity modulus μ as coefficients. The parameters ρ and μ are known to be positive and constant everywhere outside some compact domain D ? ?², but they are unknown inside D. The problem of determining these coefficients in D via information, given on the boundary of the domain D for some finite time interval, about a solution of two direct problems is considered. An estimate of the conditional stability of a solution of the inverse problem under consideration is established.     

The class of solenoidal planar-helical vector fields

The class of solenoidal vector fields whose lines lie in planes parallel to R ² is constructed by the method of mappings. This class exhausts the set of all smooth planarhelical solutions of Gromeka’s problem in some domain D ? R ³. In the case of domains D with cylindrical boundaries whose generators are orthogonal to R ², it is shown that the choice of a specific solution from the constructed class is reduced to the Dirichlet problem with respect to two functions that are harmonic conjugates in D ² = D∩R ²; i.e., Gromeka’s nonlinear problem is reduced to linear boundary value problems. As an example, a specific solution of the problem for an axisymmetric layer is presented. The solution is based on solving Dirichlet problems in the form of series uniformly convergent in \(\bar D^2\) in terms of wavelet systems that form bases of various spaces of functions harmonic in D ².     

Due-date assignment with asymmetric earliness–tardiness cost

The problem of minimizing the maximal weighted absolute lateness (MWAL) is known to be NP-hard. The due-date assignment part of MWAL for a given sequence has been shown in the literature to be solved on a single machine in O(n²) time. In this paper, we study a more general version of the problem with asymmetric cost (nonidentical earliness and tardiness weights). We introduce a linear-programming-based O(n) solution for this case. We also extend our proposed solution procedure to other machine settings such as flow-shop and parallel machines.     

The Cauchy problem for operators with injective symbol in the Lebesgue space <Emphasis Type="Italic">L</Emphasis><Superscript>2</Superscript> in a domain

Let D be a bounded domain in ? ⁿ (n ≥ 2) with infinitely smooth boundary ?D. We give some necessary and sufficient conditions for the Cauchy problem to be solvable in the Lebesgue space L ²(D) in D for an arbitrary differential operator A having an injective principal symbol. Furthermore, using bases with double orthogonality, we construct Carleman’s formula that restores a (vector-)function in L ²(D) from the Cauchy data given on a relatively open connected set Γ ? ?D and the values Au in D whenever the data belong to L ²(Γ) and L ²(D) respectively.     

Weighted fractional Bernstein’s inequalities and their applications

This paper studies the weighted, fractional Bernstein inequality for spherical polynomials on S^d-1\(\left( {0.1} \right)\;{\left\| {{{\left( { - {\Delta _0}} \right)}^{{\raise0.7ex\hbox{$r$} \!\mathord{\left/ {\vphantom {r 2}}\right.\kern-\nulldelimiterspace}\!\lower0.7ex\hbox{$2$}}}}f} \right\|_{p,w}} \leqslant {C_w}{n^r}{\left\| f \right\|_{p,w}}\;for\;all\;f \in \Pi _n^d\), where Π_n^d denotes the space of all spherical polynomials of degree at most n on S^d-1 and (-Δ₀)^r/2 is the fractional Laplacian-Beltrami operator on S^d-1. A new class of doubling weights with conditions weaker than the A_p condition is introduced and used to characterize completely those doubling weights w on S^d-1 for which the weighted Bernstein inequality (0.1) holds for some 1 ≤ p ≤ 8 and all r > t. It is shown that in the unweighted case, if 0 < p < 8 and r > 0 is not an even integer, (0.1) with w = 1 holds if and only if r > (d - 1)((1/p) - 1). As applications, we show that every function f ∈ L_p(S^d-1) with 0 < p < 1 can be approximated by the de la Vallée Poussin means of a Fourier-Laplace series and establish a sharp Sobolev type embedding theorem for the weighted Besov spaces with respect to general doubling weights.     

Structure of multiple solutions for nonlinear differential equations

Based on the eigensystem {λ_j,φ_j} of -Δ, the multiple solutions for nonlinear problem Δu + f(u) = 0 in Ω,u = 0 on ?Ω are approximated. A new search-extension method (SEM), which consists of three steps in three level subspaces, is proposed. Numerical simulations for several typical nonlinear cases, i.e. f(u) = u ³, u ², (u - p), u ²(u ² - p), are completed and some conjectures are presented.     

Parabolic equation with a singular potential

We study the existence of a nonnegative generalized solution of an initial-boundary value problem for the heat equation with a singular potential in an arbitrary bounded domain Ω ? R ⁿ , n ≥ 3, containing the unit ball. We show that if the condition ∝ _Ω V ^n/2+s |x| ^s dx ≤ c _n is satisfied for some s ≥ 0 and c _n = c _n (n, s, Ω) > 0, then the problem in question has a nonnegative solution.     

Numerical ranges for pairs of operators,duality mappings with gauge function,and spectra of nonlinear operators

We define and study numerical ranges for pairs of nonlinear operators F and J which act between some Banach space X and its dual X*, with respect to some increasing gauge function φ. Connections with spectra for certain classes of nonlinear operators introduced recently in the literature are also established. As a sample example, we consider the case when F is the duality map of the Lebesgue space L ^p (Ω), J is the duality map of the corresponding Sobolev space W ₀ ^1,p (Ω), and φ(t)=t ^p?1 (1<p<∞). This leads to existence, uniqueness, and perturbation results for a homogeneous eigenvalue problem involving the p-Laplace operator.     

Quasirecognition by prime graph of the simple group <Superscript>2</Superscript><Emphasis Type="Italic">G</Emphasis><Subscript>2</Subscript>(<Emphasis Type="Italic">q</Emphasis>)

Let G be a finite group. The main result of this paper is as follows: If G is a finite group, such that Γ(G) = Γ(²G₂(q)), where q = 3²ⁿ⁺¹ for some n ≥ 1, then G has a (unique) nonabelian composition factor isomorphic to ² G ₂(q). We infer that if G is a finite group satisfying |G| = |² G ₂(q)| and Γ(G) = Γ (² G ₂(q)) then G ? = ² G ₂(q). This enables us to give new proofs for some theorems; e.g., a conjecture of W. Shi and J. Bi. Some applications of this result are also considered to the problem of recognition by element orders of finite groups.     

Boundedness in a chemotaxis system with nonlinear signal production

This work deals with the zero-Neumann boundary problem to a fully parabolic chemotaxis system with a nonlinear signal production function f(s) fulfilling 0 ≤ f(s) ≤ Ks~α for all s ≥ 0, where K and α are positive parameters. It is shown that whenever 0 α 2/n(where n denotes the spatial dimension) and under suitable assumptions on the initial data,this problem admits a unique global classical solution that is uniformly-in-time bounded in any spatial dimension. The proof is based on some a priori estimate techniques.     

Difference scheme for an initial–boundary value problem for a singularly perturbed transport equation

An initial–boundary value problem for a singularly perturbed transport equation with a perturbation parameter ε multiplying the spatial derivative is considered on the set ? = G ∪ S, where ? = D? × [0 ≤ t ≤ T], D? = {0 ≤ x ≤ d}, S = S ^l ∪ S, and S ^l and S₀ are the lateral and lower boundaries. The parameter ε takes arbitrary values from the half-open interval (0,1]. In contrast to the well-known problem for the regular transport equation, for small values of ε, this problem involves a boundary layer of width O(ε) appearing in the neighborhood of S ^l ; in the layer, the solution of the problem varies by a finite value. For this singularly perturbed problem, the solution of a standard difference scheme on a uniform grid does not converge ε-uniformly in the maximum norm. Convergence occurs only if h=dN^-1 ? ε and N₀^-1 ? 1, where N and N₀ are the numbers of grid intervals in x and t, respectively, and h is the mesh size in x. The solution of the considered problem is decomposed into the sum of regular and singular components. With the behavior of the singular component taken into account, a special difference scheme is constructed on a Shishkin mesh, i.e., on a mesh that is piecewise uniform in x and uniform in t. On such a grid, a monotone difference scheme for the initial–boundary value problem for the singularly perturbed transport equation converges ε-uniformly in the maximum norm at an ?(N^?1 + N₀^?1) rate.     

2-Recognizability by prime graph of <Emphasis Type="Italic">PSL</Emphasis>(2, <Emphasis Type="Italic">p</Emphasis><Superscript>2</Superscript>)

Let G be a finite group and let Γ(G) be the prime graph of G. Assume p prime. We determine the finite groups G such that Γ(G) = Γ(PSL(2, p ²)) and prove that if p ≠ 2, 3, 7 is a prime then k(Γ(PSL(2, p ²))) = 2. We infer that if G is a finite group satisfying |G| = |PSL(2, p ²)| and Γ(G) = Γ(PSL(2, p ²)) then G ? PSL(2, p ²). This enables us to give new proofs for some theorems; e.g., a conjecture of W. Shi and J. Bi. Some applications are also considered of this result to the problem of recognition of finite groups by element orders.     

The manifold of isospectral symmetric tridiagonal matrices and realization of cycles by aspherical manifolds

We consider the classical N. Steenrod’s problem of realization of cycles by continuous images of manifolds. Our goal is to find a class \(\mathcal{M}_n \) of oriented n-dimensional closed smooth manifolds such that each integral homology class can be realized with some multiplicity by an image of a manifold from the class \(\mathcal{M}_n \). We prove that as the class \(\mathcal{M}_n \) one can take a set of finite-fold coverings of the manifold M ⁿ of isospectral symmetric tridiagonal real (n + 1) × (n + 1) matrices. It is well known that the manifold M ⁿ is aspherical, its fundamental group is torsion-free, and its universal covering is diffeomorphic to ? ⁿ . Thus, every integral homology class of an arcwise connected space can be realized with some multiplicity by an image of an aspherical manifold with a torsion-free fundamental group. In particular, for any closed oriented manifold Q ⁿ , there exists an aspherical manifold that has torsion-free fundamental group and can be mapped onto Q ⁿ with nonzero degree.     

On one test for the switching separability of graphs modulo <Emphasis Type="Italic">q</Emphasis>

We consider graphs whose edges are marked by numbers (weights) from 1 to q - 1 (with zero corresponding to the absence of an edge). A graph is additive if its vertices can be marked so that, for every two nonadjacent vertices, the sum of the marks modulo q is zero, and for adjacent vertices, it equals the weight of the corresponding edge. A switching of a given graph is its sum modulo q with some additive graph on the same set of vertices. A graph on n vertices is switching separable if some of its switchings has no connected components of size greater than n - 2. We consider the following separability test: If removing any vertex from G leads to a switching separable graph then G is switching separable. We prove this test for q odd and characterize the set of exclusions for q even. Connection is established between the switching separability of a graph and the reducibility of the n-ary quasigroup constructed from the graph.     

An approximation scheme for a problem of search for a vector subset

We consider the following clustering problem: Given a vector set, find a subset of cardinality k and minimum square deviation from its mean. The distance between the vectors is defined by the Euclideanmetric. We present an approximation scheme (PTAS) that allows us to solve this problem with an arbitrary relative error ? in time O(n ^2/?+1(9/?)^3/? d), where n is the number of vectors of the input set and d denotes the dimension of the space.     

Solvability of the problem of taking the discrete logarithm

It is proved that consideration of the solvability problem for taking the discrete logarithm in a residue ring modulo composite M can be reduced to consideration of a similar problem in residue rings modulo pq, where p and q are prime divisors of M. For moduli of form pq, necessary and sufficient conditions for solvability checking are obtained in some cases. In addition, the problem of raising a solution of an exponential comparison in a residue ring modulo p ^α is solved.     

Construction of Carleman formulas by using mixed problems with parameter-dependent boundary conditions

Let D be an open connected subset of the complex plane C with sufficiently smooth boundary ?D. Perturbing the Cauchy problem for the Cauchy–Riemann system ??u = f in D with boundary data on a closed subset S ? ?D, we obtain a family of mixed problems of the Zaremba-type for the Laplace equation depending on a small parameter ε ∈ (0, 1] in the boundary condition. Despite the fact that the mixed problems include noncoercive boundary conditions on ?D\S, each of them has a unique solution in some appropriate Hilbert space H ⁺(D) densely embedded in the Lebesgue space L ₂(?D) and the Sobolev–Slobodetski? space H ^1/2?δ(D) for every δ > 0. The corresponding family of the solutions {u _ε} converges to a solution to the Cauchy problem in H ⁺(D) (if the latter exists). Moreover, the existence of a solution to the Cauchy problem in H ⁺(D) is equivalent to boundedness of the family {u _ε} in this space. Thus, we propose solvability conditions for the Cauchy problem and an effective method of constructing a solution in the form of Carleman-type formulas.     

Geometry and inequalities of geometric mean

We study some geometric properties associated with the t-geometric means A ?_tB:= A^1/2(A^?1/2BA^?1/2)^tA^1/2 of two n × n positive definite matrices A and B. Some geodesical convexity results with respect to the Riemannian structure of the n × n positive definite matrices are obtained. Several norm inequalities with geometric mean are obtained. In particular, we generalize a recent result of Audenaert (2015). Numerical counterexamples are given for some inequality questions. A conjecture on the geometric mean inequality regarding m pairs of positive definite matrices is posted.