Expanding operators for the independent set problem

The notion is introduced of an expanding operator for the independent set problem. This notion is a useful tool for the constructive formation of new cases with the efficient solvability of this problem in the family of hereditary classes of graphs and is applied to hereditary parts of the set Free({P ₅, C ₅}). It is proved that if for a connected graph G the problem is polynomial-time solvable in the class Free({P ₅, C ₅,G}) then it remains so in the class Free({P ₅, C ₅,G ○ \(\bar K_2 \), G ⊕ K _1,p ) for every p. We also find two new hereditary subsets of Free({P ₅, C ₅}) with polynomially solvable independent set problem that are not a corollary of applying the revealed operators.     

Boundary value problem for one evolution equation

The aim of the paper is to investigate the boundary value problem of the evolution equation Lu = K (x,t) _ut - Δu + a (x,t) u = f (x,t). The characteristic property of this type of equations is the failure of the Petrovski’s “A” condition when coefficients are constant [1]. In this case, Cauchy problem is incorrect in the sense of Hadamard. Hence in this paper, the space, guaranteeing the correctness of the boundary value problem in the sense of Hadamard, is selected by adding some additional conditions to the coefficients of the equation.     

On a recursive inverse eigenvalue problem

Let s ₁, ..., s _n be arbitrary complex scalars. It is required to construct an n × n normal matrix A such that s _i is an eigenvalue of the leading principal submatrix A _i , i = 1, 2, ..., n. It is shown that, along with the obvious diagonal solution diag(s ₁, ..., s _n ), this problem always admits a much more interesting nondiagonal solution A. As a rule, this solution is a dense matrix; with the diagonal solution, it shares the property that each submatrix A _i is itself a normal matrix, which implies interesting connections between the spectra of the neighboring submatrices A _i and A _{i + 1}.     

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.     

On the solvability of the first nonlocal boundary value problem for an elliptic equation

We consider problems of the existence, uniqueness, and sign-definiteness of the classical solutions of the problem

$(Lu)(x) = f(x)(x \in D),u(x) - \beta (x)u(\sigma x) = \psi (x)(x \in S),$

where L is a linear second-order operator elliptic in the closure of a domain D ? R ⁿ and σ is a single-valued continuous mapping of S ≡ ?D into \(\bar D\).

We show that, under natural assumptions on the smoothness of β, σ, and the coefficients of L, this problem is Fredholm provided that either σ has no attractors on S or σ generates an attractor Θ on S and the spectral radius of the operator A defined on η(x) ∈ C(Θ) by the formula (Aη)(x) = |β(x)|η(σx) is less than unity.We obtain semieffective (in terms of a test function) conditions for the unique solvability of the problem.     

On a singular minimizing problem

We investigate the non-homogeneous modular Dirichlet problem Δ _p (·)u(x) = f (x) (where Δ _p (·)u(x) = div(|?u|^p(x-2)?u(x)) from the functional analytic point of view and we prove the stability of the solutions \({\left( {{u_{{p_i}}}} \right)_i}\) of the equation \({\Delta _{{p_i}\left( \cdot \right)}}{u_{{p_i}\left( \cdot \right)}} = f\) as p _i (·) → q(·) via Gamma-convergence of sequence of appropriate functionals.     

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.     

On an open problem of Guo-Skiba

Let G be a finite group, and let A be a proper subgroup of G. Then any chief factor H/A _G of G is called a G-boundary factor of A. For any Gboundary factor H/A _G of A, the subgroup (A ∩ H)/A _G of G/ A _G is called a G-trace of A. In this paper, we prove that G is p-soluble if and only if every maximal chain of G of length 2 contains a proper subgroup M of G such that either some G-trace of M is subnormal or every G-boundary factor of M is a p′-group. This result give a positive answer to a recent open problem of Guo and Skiba. We also give some new characterizations of p-hypercyclically embedded subgroups.     

New heuristics for flow shop problem to minimize makespan

This paper investigates the flow shop problem with the objective to minimizemakespan. New algorithms are designed: one is off-line heuristic, Single JobFirst, for problemF _m ∥C _max ;and the other is on-line heuristic, Dynamic Single Job First (DSJF), for problemF _m |r _i |C _max and its on-line version. It is proved that the two heuristics are asymptoticallyoptimal when the size of the problem is large enough. In addition, theasymptotical optimality of First-Come, First-Served manner is obtained as abyproduct of the asymptotical analysis of DSJF heuristic. At the end of thepaper, a new lower bound with performance guarantee is provided for problemF _m ∥C _max , andcomputational experiments show the effectiveness of these heuristicalgorithms.     

Fast separation for the three-index assignment problem

A critical step in a cutting plane algorithm is separation, i.e., establishing whether a given vector x violates an inequality belonging to a specific class. It is customary to express the time complexity of a separation algorithm in the number of variables n. Here, we argue that a separation algorithm may instead process the vector containing the positive components of x,  denoted as supp(x),  which offers a more compact representation, especially if x is sparse; we also propose to express the time complexity in terms of |supp(x)|. Although several well-known separation algorithms exploit the sparsity of x,  we revisit this idea in order to take sparsity explicitly into account in the time-complexity of separation and also design faster algorithms. We apply this approach to two classes of facet-defining inequalities for the three-index assignment problem, and obtain separation algorithms whose time complexity is linear in |supp(x)| instead of n. We indicate that this can be generalized to the axial k-index assignment problem and we show empirically how the separation algorithms exploiting sparsity improve on existing ones by running them on the largest instances reported in the literature.     

Convergence rates for Tikhonov regularization of a two-coefficient identification problem in an elliptic boundary value problem

We investigate the convergence rates for Tikhonov regularization of the problem of simultaneously estimating the coefficients q and a in the Neumann problem for the elliptic equation \({{-{\rm div}(q \nabla u) + au = f \;{\rm in}\; \Omega, q{\partial u}/{\partial n} = g}}\) on the boundary \({{\partial\Omega, \Omega \subset \mathbb{R}^d, d \geq 1}}\) , when u is imprecisely given by \({{{z^\delta} \in {H^1}(\Omega), \|u-z^\delta\|_{H^1(\Omega)}\le\delta, \delta > 0}}\). We regularize this problem by minimizing the strictly convex functional of (q, a)

$\begin{array}{lll}\int\limits_{\Omega}\left(q| \nabla (U(q,a)-z^{\delta})|^2 + a(U(q,a)-z^{\delta})^2\right)dx\\\quad+\rho\left(\|q-q^*\|^2_{L^2(\Omega)} + \|a-a^*\|^2_{L^2(\Omega)}\right)\end{array}$

over the admissible set K, where ρ > 0 is the regularization parameter and (q*, a*) is an a priori estimate of the true pair (q, a) which is identified, and consider the unique solution of these minimization problem as the regularized one to that of the inverse problem. We obtain the convergence rate \({{{\mathcal {O}}(\sqrt{\delta})}}\), as δ → 0 and ρ ~ δ, for the regularized solutions under the simple and weak source condition

${\rm there\;is\;a\;function}\;w^* \in V^*\;{\rm such\;that}\;{U^\prime (q^ \dagger, a^\dagger)}^*w^* = (q^\dagger - q^*, a^\dagger - a^*)$

with \({{(q^\dagger, a^\dagger)}}\) being the (q*, a*)-minimum norm solution of the coefficient identification problem, U′(·, ·) the Fréchet derivative of U(·, ·), V the Sobolev space on which the boundary value problem is considered. Our source condition is without the smallness requirement on the source function which is popularized in the theory of regularization of nonlinear ill-posed problems. Furthermore, some concrete cases of our source condition are proved to be simply the requirement that the sought coefficients belong to certain smooth function spaces.

     

The connected <Emphasis Type="Italic">p</Emphasis>-median problem on block graphs

In this paper, we study a variant of the p-median problem on block graphs G in which the p-median is asked to be connected, and this problem is called the connected p-median problem. We first show that the connected p-median problem is NP-hard on block graphs with multiple edge weights. Then, we propose an O(n)-time algorithm for solving the problem on unit-edge-weighted block graphs, where n is the number of vertices in G.     

A short note on Lq theory for Stokes problem with a pressure-dependent viscosity

We study higher local integrability of a weak solution to the steady Stokes problem. We consider the case of a pressure- and shear-rate-dependent viscosity, i.e., the elliptic part of the Stokes problem is assumed to be nonlinear and it depends on p and on the symmetric part of a gradient of u, namely, it is represented by a stress tensor T (Du, p):= v(p, |D|²)D which satisfies r-growth condition with r ∈ (1, 2]. In order to get the main result, we use Calderón-Zygmund theory and the method which was presented for example in the paper Caffarelli, Peral (1998).     

Eigenvalue analysis of constrained minimization problem for homogeneous polynomial

In this paper, the concepts of Pareto H-eigenvalue and Pareto Z-eigenvalue are introduced for studying constrained minimization problem and the necessary and sufficient conditions of such eigenvalues are given. It is proved that a symmetric tensor has at least one Pareto H-eigenvalue (Pareto Z-eigenvalue). Furthermore, the minimum Pareto H-eigenvalue (or Pareto Z-eigenvalue) of a symmetric tensor is exactly equal to the minimum value of constrained minimization problem of homogeneous polynomial deduced by such a tensor, which gives an alternative methods for solving the minimum value of constrained minimization problem. In particular, a symmetric tensor \({\mathcal {A}}\) is strictly copositive if and only if every Pareto H-eigenvalue (Z-eigenvalue) of \({\mathcal {A}}\) is positive, and \({\mathcal {A}}\) is copositive if and only if every Pareto H-eigenvalue (Z-eigenvalue) of \({\mathcal {A}}\) is non-negative.     

A new heuristic approach for the P-median problem

The Euclidean p-median problem is concerned with the decision of the locations for public service centres. Existing methods for the planar Euclidean p-median problems are capable of efficiently solving problems of relatively small scale. This paper proposes two new heuristic algorithms aiming at problems of large scale. Firstly, to reflect the different degrees of proximity to optimality, a new kind of local optimum called level-m optimum is defined. For a level-m optimum of a p-median problem, where m<p, each of its subsets containing m of the p partitions is a global optimum of the corresponding m-median subproblem. Starting from a conventional local optimum, the first new algorithm efficiently improves it to a level-2 optimum by applying an existing exact algorithm for solving the 2-median problem. The second new algorithm further improves it to a level-3 optimum by applying a new exact algorithm for solving the 3-median problem. Comparison based on experimental results confirms that the proposed algorithms are superior to the existing heuristics, especially in terms of solution quality.     

On the Cauchy problem for an Emden-Fowler equation

We consider the equation y″ = P(x)x ^a y ^σ , σ < 0, and prove the unique solvability of the Cauchy problem y(0) = 0, y′(0) = λ.     

Approximation algorithms for the robust facility leasing problem

In this paper, we consider the robust facility leasing problem (RFLE), which is a variant of the well-known facility leasing problem. In this problem, we are given a facility location set, a client location set of cardinality n, time periods \(\{1, 2, \ldots , T\}\) and a nonnegative integer \(q < n\). At each time period t, a subset of clients \(D_{t}\) arrives. There are K lease types for all facilities. Leasing a facility i of a type k at any time period s incurs a leasing cost \(f_i^{k}\) such that facility i is opened at time period s with a lease length \(l_k\). Each client in \(D_t\) can only be assigned to a facility whose open interval contains t. Assigning a client j to a facility i incurs a serving cost \(c_{ij}\). We want to lease some facilities to serve at least \(n-q\) clients such that the total cost including leasing and serving cost is minimized. Using the standard primal–dual technique, we present a 6-approximation algorithm for the RFLE. We further offer a refined 3-approximation algorithm by modifying the phase of constructing an integer primal feasible solution with a careful recognition on the leasing facilities.     

The Corona problem on a complete ultrametric algebraically closed field

Let IK be a complete ultrametric algebraically closed field and let A be the Banach IK-algebra of bounded analytic functions in the ”open” unit disk D of IK provided with the Gauss norm. Let Mult(A, ‖. ‖) be the set of continuous multiplicative semi-norms of A provided with the topology of simple convergence, let Mult _m (A, ‖. ‖) be the subset of the ? ∈ Mult(A, ‖. ‖) whose kernel is amaximal ideal and let Mult ₁(A, ‖. ‖) be the subset of the ? ∈ Mult(A, ‖. ‖) whose kernel is a maximal ideal of the form (x ? a)A with a ∈ D. By analogy with the Archimedean context, one usually calls ultrametric Corona problem the question whether Mult ₁(A, ‖. ‖) is dense in Mult _m (A, ‖. ‖). In a previous paper, it was proved that when IK is spherically complete, the answer is yes. Here we generalize this result to any algebraically closed complete ultrametric field, which particularly applies to ? _p . On the other hand, we also show that the continuous multiplicative seminorms whose kernel are neither a maximal ideal nor the zero ideal, found by Jesus Araujo, also lie in the closure of Mult ₁(A, ‖. ‖), which suggest that Mult ₁(A, ‖. ‖)might be dense in Mult(A, ‖. ‖).     

Propagation of waves in a randomly stratified medium: An inverse problem

We pose and solve an inverse problem of finding a coefficient in the wave equation in the inhomogeneous semispace on the scattering data of a plane wave incident from the homogeneous semispace. The unknown coefficient is a sum of a deterministic summand of one variable (the “depth” z) and a small random summand α(x, z). We look for the deterministic summand, the expectation E(α(x, z)) =: m(z), and the second moment r(x ₁ t - x ₂, z ₁, z ₂):= E(α(x ₁, z ₁)α(x ₂, z ₂)). Here the symbol E(·) stands for expectation. The stratification property of a medium means that (i) the deterministic summand depends only on z, (ii) m(z) depends only on z, and (iii) the second moment for fixed z ₁ and z ₂ depends only on x ₁ ? x ₂.