Constant-factor approximations for Capacitated Arc Routing without triangle inequality

Given an undirected graph with edge costs and edge demands, the Capacitated Arc Routing problem (CARP) asks for minimum-cost routes for equal-capacity vehicles so as to satisfy all demands. Constant-factor polynomial-time approximation algorithms were proposed for CARP with triangle inequality, while CARP was claimed to be NP-hard to approximate within any constant factor in general. Correcting this claim, we show that any factor  α$\alpha$ approximation for CARP with triangle inequality yields a factor  α$\alpha$ approximation for the general CARP.     

An eigenvalue problem for derogatory matrices

A matrix A is called derogatory   if there is more than one Jordan submatrix associated with an eigenvalue λ$\lambda$. In this paper, we are concerned with the eigenvalue problem of this type of matrices.     

Recursive approximation of the dominant eigenspace of an indefinite matrix

We consider here the problem of tracking the dominant eigenspace of an indefinite matrix by updating recursively a rank k$k$ approximation of the given matrix. The tracking uses a window of the given matrix, which increases at every step of the algorithm. Therefore, the rank of the approximation increases also, and hence a rank reduction of the approximation is needed to retrieve an approximation of rank k$k$. In order to perform the window adaptation and the rank reduction in an efficient manner, we make use of a new anti-triangular decomposition for indefinite matrices. All steps of the algorithm only make use of orthogonal transformations, which guarantees the stability of the intermediate steps. We also show some numerical experiments to illustrate the performance of the tracking algorithm.     

Constant-sign and sign-changing solutions for nonlinear eigenvalue problems

We prove the existence of multiple constant-sign and sign-changing solutions for a nonlinear elliptic eigenvalue problem under Dirichlet boundary condition involving the p$p$-Laplacian. More precisely, we establish the existence of a positive solution, of a negative solution, and of a nontrivial sign-changing solution when the eigenvalue parameter λ$\lambda$ is greater than the second eigenvalue _λ2${\lambda }_2$ of the negative p$p$-Laplacian, extending results by Ambrosetti–Lupo, Ambrosetti–Mancini, and Struwe. Our approach relies on a combined use of variational and topological tools (such as, e.g., critical points, Mountain-Pass theorem, second deformation lemma, variational characterization of the first and second eigenvalue of the p$p$-Laplacian) and comparison arguments for nonlinear differential inequalities. In particular, the existence of extremal nontrivial constant-sign solutions plays an important role in the proof of sign-changing solutions.     

A sharp upper bound on the signless Laplacian spectral radius of graphs

Let G be a simple connected graph of order n   with degree sequence _d1,_d2,…,_dn$d_1,d_2,\dots ,d_n$ in non-increasing order. The signless Laplacian spectral radius ρ(Q(G))$\rho (Q(G))$ of G   is the largest eigenvalue of its signless Laplacian matrix Q(G)$Q(G)$. In this paper, we give a sharp upper bound on the signless Laplacian spectral radius ρ(Q(G))$\rho (Q(G))$ in terms of _di$d_i$, which improves and generalizes some known results.     

UNIVERSAL BOUNDS FOR EIGENVALUES OF LAPLACIAN OPERATOR OF ANY ORDER

Let Ω be a connected bounded domain in Rn. Denote by λi the i-th eigenvalue of the Laplacian operator with any order p:{0(-△)pu =λu u =■u/→■n =···=■→■np-1 p-u1=0 in Ω,on ■Ω.In this article, we give some expressions for upper bound of the (k + 1)-th eigenvalue λk+1 in terms of the first k eigenvalues.     

An efficient algorithm for the Schrödinger–Poisson eigenvalue problem

We present a new implementation of the two-grid method for computing extremum eigenpairs of self-adjoint partial differential operators with periodic boundary conditions. A novel two-grid centered difference method is proposed for the numerical solutions of the nonlinear Schrödinger–Poisson (SP) eigenvalue problem.We solve the Poisson equation to obtain the nonlinear potential for the nonlinear Schrödinger eigenvalue problem, and use the block Lanczos method to compute the first k   eigenpairs of the Schrödinger eigenvalue problem until they converge on the coarse grid. Then we perform a few conjugate gradient iterations to solve each symmetric positive definite linear system for the approximate eigenvector on the fine grid. The Rayleigh quotient iteration is exploited to improve the accuracy of the eigenpairs on the fine grid. Our numerical results show how the first few eigenpairs of the Schrödinger eigenvalue problem are affected by the dopant in the Schrödinger–Poisson (SP) system. Moreover, the convergence rate of eigenvalue computations on the fine grid is O(h³)$\mathrm{O}(h^3)$.     

A Jacobi–Davidson type method for the product eigenvalue problem

We propose a Jacobi–Davidson type method to compute selected eigenpairs of the product eigenvalue problem _Am?_A1x=λx,$A_m?A_{1}x=\lambda x,$ where the matrices may be large and sparse. To avoid difficulties caused by a high condition number of the product matrix, we split up the action of the product matrix and work with several search spaces. We generalize the Jacobi–Davidson correction equation and the harmonic and refined extraction for the product eigenvalue problem. Numerical experiments indicate that the method can be used to compute eigenvalues of product matrices with extremely high condition numbers.     

A proximal bundle method with inexact data for convex nondifferentiable minimization

A proximal bundle method with inexact data is presented for minimizing an unconstrained nonsmooth convex function f$f$. At each iteration, only the approximate evaluations of f$f$ and its ε$\epsilon$-subgradients are required and its search directions are determined via solving quadratic programmings. Compared with the pre-existing results, the polyhedral approximation model that we offer is more precise and a new term is added into the estimation term of the descent from the model. It is shown that every cluster of the sequence of iterates generated by the proposed algorithm is an exact solution of the unconstrained minimization problem.     

A transfer integral technique for solving a class of linear integral equations: Convergence and applications to DNA

An eigenvalue problem, the convergence difficulties that arise and a mathematical solution are considered. The eigenvalue problem is motivated by simplified models for the dissociation equilibrium between double-stranded and single-stranded DNA chains induced by temperature (thermal denaturation), and by the application of the so-called transfer integral technique. Namely, we extend the Peyrard–Bishop model for DNA melting from the original one-dimensional model to a three-dimensional one, which gives rise to an eigenvalue problem defined by a linear integral equation whose kernel is not in L²$L^2$. For the one-dimensional model, the corresponding kernel is not in L²$L^2$ either, which is related to certain convergence difficulties noticed by previous researchers. Inspired by methods from quantum scattering theory, we transform the three-dimensional eigenvalue problem, obtaining a new L²$L^2$ kernel which has improved convergence properties.     

Regularity in a one-phase free boundary problem for the fractional Laplacian

For a one-phase free boundary problem involving a fractional Laplacian, we prove that “flat free boundaries” are C^1,α$C^{1,\alpha }$. We recover the regularity results of Caffarelli for viscosity solutions of the classical Bernoulli-type free boundary problem with the standard Laplacian.     

Low lying eigenvalues of randomly curved quantum waveguides

We consider the negative Dirichlet Laplacian on an infinite waveguide embedded in R²${\mathbb{R}}^2$, and finite segments thereof. The waveguide is a perturbation of a periodic strip in terms of a sequence of independent identically distributed random variables which influence the curvature. We derive explicit lower bounds on the first eigenvalue of finite segments of the randomly curved waveguide in the small coupling (i.e. weak disorder) regime. This allows us to estimate the probability of low lying eigenvalues, a tool which is relevant in the context of Anderson localization for random Schrödinger operators.     

Quasi-polynomial tractability of linear problems in the average case setting

We study d$d$-variate approximation problems in the average case setting with respect to a zero-mean Gaussian measure. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. For the absolute error criterion, we obtain the necessary and sufficient conditions in terms of the eigenvalues of its covariance operator and obtain an estimate of the exponent t^qpol-avg$t^{\text{qpol-avg}}$ of quasi-polynomial tractability which cannot be improved in general. For the linear tensor product problems, we find that the quasi-polynomial tractability is equivalent to the strong polynomial tractability. For the normalized error criterion, we solve a problem related to the Korobov kernels, which is left open in Lifshits et al. (2012).     

Preconditioned Lanczos method for generalized Toeplitz eigenvalue problems

We employ the sine transform-based preconditioner to precondition the shifted Toeplitz matrix _An−ρ_Bn$A_n-\rho B_n$ involved in the Lanczos method to compute the minimum eigenvalue of the generalized symmetric Toeplitz eigenvalue problem _Anx=λ_Bnx$A_{n}x=\lambda B_{n}x$, where _An$A_n$ and _Bn$B_n$ are given matrices of suitable sizes. The sine transform-based preconditioner can improve the spectral distribution of the shifted Toeplitz matrix and, hence, can speed up the convergence rate of the preconditioned Lanczos method. The sine transform-based preconditioner can be implemented efficiently by the fast transform algorithm. A convergence analysis shows that the preconditioned Lanczos method converges sufficiently fast, and numerical results show that this method is highly effective for a large matrix.     

An improved grid method for the computation of the pseudospectra of matrix polynomials

Pseudospectra of matrix polynomials have been systematically investigated in recent years, since they provide important insights into the sensitivity of polynomial eigenvalue problems. An accurate approximation of the pseudospectrum of a matrix polynomial $P\left(\lambda \right)$ by means of the standard grid method is highly demanding computationally. In this paper, we propose an improvement of the grid method, which reduces the computational cost and retains the robustness and the parallelism of the method. In particular, after giving two lower bounds for the distance from a point to the boundary of the pseudospectrum of $P\left(\lambda \right)$, we present two algorithms for the estimation of the pseudospectrum, using exclusion discs. Furthermore, two illustrative examples and an application of pseudospectra on elliptic (quadratic) eigenvalue problems are given.