An exact algorithm for finding a vector subset with the longest sum

We consider the problem: Given a set of n vectors in the d-dimensional Euclidean space, find a subsetmaximizing the length of the sum vector.We propose an algorithm that finds an optimal solution to this problem in time O(n^d?1(d + logn)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.     

Construction of optimal quadrature formulas for Fourier coefficients in Sobolev space $L_{2}^{(m)}(0,1)$

This paper studies the problem of construction of optimal quadrature formulas in the sense of Sard in the \(L_{2}^{(m)}(0,1)\) space for numerical calculation of Fourier coefficients. Using the S.L.Sobolev’s method, we obtain new optimal quadrature formulas of such type for N+1≥m, where N+1 is the number of nodes. Moreover, explicit formulas for the optimal coefficients are obtained. We study the order of convergence of the optimal formula for the case m=1. The obtained optimal quadrature formulas in the \(L_{2}^{(m)}(0,1)\) space are exact for P _m?1(x), where P _m?1(x) is a polynomial of degree m?1. Furthermore, we present some numerical results, which confirm the obtained theoretical results.     

Parametric AE-solution sets to the parametric linear systems with multiple right-hand sides and parametric matrix equation A(p)X = B(p)

In this paper, the parametric matrix equation A(p)X = B(p) whose elements are linear functions of uncertain parameters varying within intervals are considered. In this matrix equation A(p) and B(p) are known m-by-m and m-by-n matrices respectively, and X is the m-by-n unknown matrix. We discuss the so-called AE-solution sets for such systems and give some analytical characterizations for the AE-solution sets and a sufficient condition under which these solution sets are bounded. We then propose a modification of Krawczyk operator for parametric systems which causes reduction of the computational complexity of obtaining an outer estimation for the parametric united solution set, considerably. Then we give a generalization of the Bauer-Skeel and the Hansen-Bliek-Rohn bounds for enclosing the parametric united solution set which also enables us to reduce the computational complexity, significantly. Also some numerical approaches based on Gaussian elimination and Gauss-Seidel methods to find outer estimations for the parametric united solution set are given. Finally, some numerical experiments are given to illustrate the performance of the proposed methods.     

Linear preservers of row-dense matrices

Let M_m,n be the set of all m × n real matrices. A matrix A ∈ M_m,n is said to be row-dense if there are no zeros between two nonzero entries for every row of this matrix. We find the structure of linear functions T: M_m,n → M_m,n that preserve or strongly preserve row-dense matrices, i.e., T(A) is row-dense whenever A is row-dense or T(A) is row-dense if and only if A is row-dense, respectively. Similarly, a matrix A ∈ M_n,m is called a column-dense matrix if every column of A is a column-dense vector. At the end, the structure of linear preservers (strong linear preservers) of column-dense matrices is found.     

Bent functions with stronger nonlinear properties: K-bent functions

We introduce the notion of k-bent function, i.e., a Boolean functionwith evennumber m of variables υ ₁, …, υ _m which can be approximated with all functions of the form 〈u, v〉 _j ⊕ a in the equally poor manner, where u ∈ ? ₂ ^m , a ∈ ?₂, and 1 ? j ? k. Here 〈·, ·〉 _j is an analog of the inner product of vectors; k changes from 1 to m/2. The operations 〈·, ·〉 _k , 1 ? k ? m/2, are defined by using the special series of binary Hadamard-like codes A _m ^k of length 2 ^m . Namely, the vectors of values for the functions 〈u, v〉 _k ⊕ a are codewords of the code A _m ^k . The codes A _m ^k are constructed using subcodes of the ?₄-linear Hadamard-like codes of length 2 ^m+1, which were classified by D. S. Krotov (2001). At that the code A _m ¹ is linear and A _m ¹ , …, A _m ^m/2 are pairwise nonequivalent. On the codewords of a code A _m ^k , we define a group operation ? coordinated with the Hamming metric. That is why we can consider k-bent functions as functions that are maximal nonlinear in k distinct senses of linearity at the same time. Bent functions in usual sense coincide with 1-bent functions. For k > ? ? 1, the class of k-bent functions is a proper subclass of the class of ?-bent functions. In the paper, we give methods for constructing k-bent functions and study their properties. It is shown that there exist k-bent functions with an arbitrary algebraic degree d, where 2 ? d ? max {2, m/2 ? k + 1}. Given an arbitrary k, we define the subset \(\mathfrak{F}_m^k \mathcal{F}_m^k \) of the set \(\mathfrak{F}_m^k \mathcal{F}_m^k \) \(\mathcal{A}_m^k \mathcal{B}_m^k \) of all Boolean functions in m variables with the following property: on this subset k-bent functions and 1-bent functions coincide.     

Non-trivial m-quasi-Einstein metrics on quadratic Lie groups

We call a metric m-quasi-Einstein if \({Ric_X^m}\) (a modification of the m-Bakry–Emery Ricci tensor in terms of a suitable vector field X) is a constant multiple of the metric tensor. It is a generalization of Einstein metrics which contain Ricci solitons. In this paper, we focus on left-invariant vector fields and left-invariant Riemannian metrics on quadratic Lie groups. First we prove that any left-invariant vector field X such that the left-invariant Riemannian metric on a quadratic Lie group is m-quasi-Einstein is a Killing vector field. Then we construct infinitely many non-trivial m-quasi-Einstein metrics on solvable quadratic Lie groups G(n) for m finite.     

The relative Chebyshev centers of finite sets in geodesic spaces

In the present paper we estimate variation in the relative Chebyshev radius R _W (M), where M and W are nonempty bounded sets of a metric space, as the sets M and W change. We find the closure and the interior of the set of all N-nets each of which contains its unique relative Chebyshev center, in the set of all N-nets of a special geodesic space endowed by the Hausdorff metric. We consider various properties of relative Chebyshev centers of a finite set which lie in this set.     

The best <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> approximation of the Laplace operator by linear bounded operators in the classes of functions of two and three variables

Close two-sided estimates are obtained for the best approximation in the space L _p (? ^m ), m = 2 and 3, 1 ≤ p ≤ ∞, of the Laplace operator by linear bounded operators in the class of functions for which the second power of the Laplace operator belongs to the space L _p (? ^m ). We estimate the best constant in the corresponding Kolmogorov inequality and the error of the optimal recovery of values of the Laplace operator on functions from this class given with an error. We present an operator whose deviation from the Laplace operator is close to the best.     

The Lipschitzianity of convex vector and set-valued functions

It is well known that every scalar convex function is locally Lipschitz on the interior of its domain in finite dimensional spaces. The aim of this paper is to extend this result for both vector functions and set-valued mappings acting between infinite dimensional spaces with an order generated by a proper convex cone C. Under the additional assumption that the ordering cone C is normal, we prove that a locally C-bounded C-convex vector function is Lipschitz on the interior of its domain by two different ways. Moreover, we derive necessary conditions for Pareto minimal points of vector-valued optimization problems where the objective function is C-convex and C-bounded. Corresponding results are derived for set-valued optimization problems.     

The Geometry of <Emphasis Type="Italic">m</Emphasis>-Hyperconvex Domains

We study the geometry of m-regular domains within the Caffarelli–Nirenberg–Spruck model in terms of barrier functions, envelopes, exhaustion functions, and Jensen measures. We prove among other things that every m-hyperconvex domain admits an exhaustion function that is negative, smooth, strictly m-subharmonic, and has bounded m-Hessian measure.     

An asymptotically optimal algorithm for the <Emphasis Type="Italic">m</Emphasis>-Peripatetic Salesman Problem on random inputs with discrete distribution

We consider the m-Peripatetic Salesman Problem (m-PSP) on random inputs with discrete distribution function. In this paper we present a polynomial approximation algorithm which, under certain conditions, with high probability (w.h.p.) gives optimal solution for both the m-PSP on random inputs with identical weight functions and the m-PSP with different weight functions.     

On ordered-covering mappings and implicit differential inequalities

We define the set of ordered covering of a mapping that acts in partially ordered spaces; we suggest a method for finding the set of ordered covering of vector functions of several variables and the Nemytskii operator acting in Lebesgue spaces. We prove assertions on operator inequalities in arbitrary partially ordered spaces. We obtain conditions that use a set of ordered covering of the corresponding mapping and ensure that the existence of an element u such that f(u) ≥ y implies the solvability of the equation f(x) = y and the estimate x ≤ u for its solution. We study the problem on the existence of the minimal and least solutions. These results are used for the analysis of an implicit differential equation. For the Cauchy problem, we prove a theorem on an inequality of the Chaplygin type.     

Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization

Recently, the alternating direction method of multipliers (ADMM) has found many efficient applications in various areas; and it has been shown that the convergence is not guaranteed when it is directly extended to the multiple-block case of separable convex minimization problems where there are m ≥ 3 functions without coupled variables in the objective. This fact has given great impetus to investigate various conditions on both the model and the algorithm’s parameter that can ensure the convergence of the direct extension of ADMM (abbreviated as “e-ADMM”). Despite some results under very strong conditions (e.g., at least (m ? 1) functions should be strongly convex) that are applicable to the generic case with a general m, some others concentrate on the special case of m = 3 under the relatively milder condition that only one function is assumed to be strongly convex. We focus on extending the convergence analysis from the case of m = 3 to the more general case of m ≥ 3. That is, we show the convergence of e-ADMM for the case of m ≥ 3 with the assumption of only (m ? 2) functions being strongly convex; and establish its convergence rates in different scenarios such as the worst-case convergence rates measured by iteration complexity and the globally linear convergence rate under stronger assumptions. Thus the convergence of e-ADMM for the general case of m ≥ 4 is proved; this result seems to be still unknown even though it is intuitive given the known result of the case of m = 3. Even for the special case of m = 3, our convergence results turn out to be more general than the existing results that are derived specifically for the case of m = 3.     

Interpolation of vector measures

Let (Ω, Σ) be a measurable space and m ₀: Σ → X ₀ and m ₁: Σ → X ₁ be positive vector measures with values in the Banach Köthe function spaces X ₀ and X ₁. If 0 < α < 1, we define a new vector measure [m ₀, m ₁] _α with values in the Calderón lattice interpolation space X ₀ ^1?ga X ₁ ^α and we analyze the space of integrable functions with respect to measure [m ₀, m ₁] _α in order to prove suitable extensions of the classical Stein-Weiss formulas that hold for the complex interpolation of L ^p -spaces. Since each p-convex order continuous Köthe function space with weak order unit can be represented as a space of p-integrable functions with respect to a vector measure, we provide in this way a technique to obtain representations of the corresponding complex interpolation spaces. As applications, we provide a Riesz-Thorin theorem for spaces of p-integrable functions with respect to vector measures and a formula for representing the interpolation of the injective tensor product of such spaces.     

Density of characters of bounded <Emphasis Type="Italic">p</Emphasis>-adic analytic functions in the topological dual

Let K be an ultrametric complete algebraically closed field, let D be a disk {x ∈ K ‖x| < R} (with R in the set of absolute values of K) and let A be the Banach algebra of bounded analytic functions in D. The vector space generated by the set of characters of A is dense in the topological dual of A if and only if K is not spherically complete. Let H(D) be the Banach algebra of analytic elements in D. The vector space generated by the set of characters of H(D) is never dense in the topological dual of H(D).     

Nonlinear separation concerning <Emphasis Type="Italic">E</Emphasis>-optimal solution of constrained multi-objective optimization problems

This paper aims at investigating optimality conditions in terms of E-optimal solution for constrained multi-objective optimization problems in a general scheme, where E is an improvement set with respect to a nontrivial closed convex point cone with apex at the origin. In the case where E is not convex, nonlinear vector regular weak separation functions and scalar weak separation functions are introduced respectively to realize the separation between the two sets in the image space, and Lagrangian-type optimality conditions are established. These results extend and improve the convex ones in the literature.     

An arithmetical equation with respect to regular convolutions

It is well known that Euler’s totient function \(\phi \) satisfies the arithmetical equation \( \phi (mn)\phi ((m, n))=\phi (m)\phi (n)(m, n) \) for all positive integers m and n, where (m, n) denotes the greatest common divisor of m and n. In this paper we consider this equation in a more general setting by characterizing the arithmetical functions f with \(f(1)\ne 0\) which satisfy the arithmetical equation \( f(mn)f((m,n)) = f(m)f(n)g((m, n)) \) for all positive integers m, n with \(m,n \in A(mn)\), where A is a regular convolution and g is an A-multiplicative function. Euler’s totient function \(\phi _A\) with respect to A is an example satisfying this equation.     

The optimal solution set of the interval linear programming problems

Several methods exist for solving the interval linear programming (ILP) problem. In most of these methods, we can only obtain the optimal value of the objective function of the ILP problem. In this paper we determine the optimal solution set of the ILP as the intersection of some regions, by the best and the worst case (BWC) methods, when the feasible solution components of the best problem are positive. First, we convert the ILP problem to the convex combination problem by coefficients 0 ≤ λ _j , μ _ij , μ _i  ≤ 1, for i = 1, 2, . . . , m and j = 1, 2, . . . , n. If for each i, j, μ _ij  = μ _i  = λ _j  = 0, then the best problem has been obtained (in case of minimization problem). We move from the best problem towards the worst problem by tiny variations of λ _j , μ _ij and μ _i from 0 to 1. Then we solve each of the obtained problems. All of the optimal solutions form a region that we call the optimal solution set of the ILP. Our aim is to determine this optimal solution set by the best and the worst problem constraints. We show that some theorems to validity of this optimal solution set.     

Finite Groups with a Given Set of Character Degrees

Let G be a finite group with {1, q, r, qm, q ² m, rqm} as the character degree set, where r and q are distinct primes and m>1 is an integer not divisible by q or r. We show that G is solvable and the derived length of G equals 3.     

A note on scheduling jobs with equal processing times and inclusive processing set restrictions

We consider the problem of scheduling n jobs on m parallel machines with inclusive processing set restrictions. Each job has a given release date, and all jobs have equal processing times. The objective is to minimize the makespan of the schedule. Li and Li (2015) have developed an O(n²+mn log?n) time algorithm for this problem. In this note, we present a modified algorithm with an improved time complexity of O(min{m, log?n} ? n log?n).