On One Method for Studying the Cauchy Problem for a Singularly Perturbed Nonlinear First-Order Differential Operator

A sequence that converges to the solution of the Cauchy problem for a singularly perturbed nonlinear first-order differential operator has been constructed. The sequence is asymptotic in the sense that any deviation (in the norm of the space of continuous functions) of its nth element from the problem solution is proportional to the (n + 1)th power of the perturbation parameter. The possibility has been shown for applying the sequence to validating an asymptotics obtained with the method of boundary functions.     

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.     

A note on a mixed routing and scheduling problem on a grid graph

We consider a particular case of the Fleet Quickest Routing Problem (FQRP) on a grid graph of m × n nodes that are placed in m levels and n columns. Starting nodes are placed at the first (bottom) level, and nodes of arrival are placed at the mth level. A feasible solution of FQRP consists in n Manhattan paths, one for each vehicle, such that capacity constraints are respected. We establish m*, i.e. the number of levels that ensures the existence of a solution to FQRP in any possible permutation of n destinations. In particular, m* is the minimum number of levels sufficient to solve any instance of FQRP involving n vehicles, when they move in the ways that the literature has until now assumed. Existing algorithms give solutions that require, for some values of n, more levels than m*. For this reason, we provide algorithm CaR, which gives a solution in a graph m* × n, as a minor contribution.     

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.     

On the summability factors of infinite series

The author has established that if [λ_n] is a convex sequence such that the series Σn ^-1λ_n is convergent and the sequence {K _n} satisfies the condition |K _n|=O[log(n+1)]^k(C, 1),k?0, whereK _n denotes the (R, logn, 1) mean of the sequence {n log (n+1)a _n}, then the series Σlog(n+1)^1-kλ_n a _n is summable |R, logn, 1|. The result obtained for the particular casek=0 generalises a previous result of the author [1].     

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}.     

On the Problem of the Optimal Choice of Record Values

Let the independent random variables X1, X2, … have the same continuous distribution function. The upper record values X(1) = X₁ < X(2) < … generated by this sequence of variables, as well as the lower record values x(1) = X₁ > x(2) > …, are considered. It is known that in this situation, the mean value c(n) of the total number of the both types of records among the first n variables X is given by the equality c(n)=2(1+1/2+…+1/n), n = 1, 2, …. The problem considered here is following: how, sequentially obtaining the observed values x₁, x₂, … of variables X and selecting one of them as the initial point, to obtain the maximal mean value e(n) of the considered numbers of records among the rest random variables. It is not possible to come back to rejected elements of the sequence. Some procedures of the optimal choice of the initial element X _r are discussed. The corresponding tables for the values e(n) and differences δ(n)= e(n)–c(n) are presented for different values of n. The value of δ= lim_n→∞δ(n)is also given. In some sense, the considered problem and optimization procedure presented in this paper are quite similar to the classical “secretary problem,” in which the probability of selecting the last record value in the set of independent identically distributed X is maximized.     

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.     

Nonlinear Schrödinger equation for the twisted Laplacian in the critical case

In [6] and [7], we prove well-posedness of solution to the nonlinear Schrödinger equation associated to the twisted Laplacian on ? ⁿ for a general class of nonlinearities including power type with subcritical case 0 ≤ α < 2/n?1. In this paper, we consider the critical case α = 2/n?1 with n ≥ 2. Our approach is based on truncation of the given nonlinearity G, which is used in [3]. We obtain solution for the truncated problem. We obtain solution to the original problem by passing to the limit.     

Maximum Distance Between Slater Orders and Copeland Orders of Tournaments

Given a tournament T?=?(X, A), we consider two tournament solutions applied to T: Slater’s solution and Copeland’s solution. Slater’s solution consists in determining the linear orders obtained by reversing a minimum number of directed edges of T in order to make T transitive. Copeland’s solution applied to T ranks the vertices of T according to their decreasing out-degrees. The aim of this paper is to compare the results provided by these two methods: to which extent can they lead to different orders? We consider three cases: T is any tournament, T is strongly connected, T has only one Slater order. For each one of these three cases, we specify the maximum of the symmetric difference distance between Slater orders and Copeland orders. More precisely, thanks to a result dealing with arc-disjoint circuits in circular tournaments, we show that this maximum is equal to n(n???1)/2 if T is any tournament on an odd number n of vertices, to (n ²???3n?+?2)/2 if T is any tournament on an even number n of vertices, to n(n???1)/2 if T is strongly connected with an odd number n of vertices, to (n ²???3n???2)/2 if T is strongly connected with an even number n of vertices greater than or equal to 8, to (n ²???5n?+?6)/2 if T has an odd number n of vertices and only one Slater order, to (n ²???5n?+?8)/2 if T has an even number n of vertices and only one Slater order.     

Solution of the NP-hard total tardiness minimization problem in scheduling theory

The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1‖ΣT _j is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. Algorithms are constructed for finding an optimal schedule depending on the number of subsets. The complexity of the algorithms is O(n ²Σp _j ), where n is the number of jobs and p _j is the processing time of the jth job (j = 1, 2, …, n).     

An Optimal Algorithm for the <Emphasis Type="Italic">k</Emphasis>-Fixed-Endpoint Path Cover on Proper Interval Graphs

In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint simple paths that covers the vertices of G, such that the vertices of T are all endpoints of these paths. The goal is to compute a k-fixed-endpoint path cover of G with minimum cardinality. We propose an optimal algorithm for this problem with runtime O(n), where n is the number of intervals in G. This algorithm is based on the Stair Normal Interval Representation (SNIR) matrix that characterizes proper interval graphs. In this characterization, every maximal clique of the graph is represented by one matrix element; the proposed algorithm uses this structural property, in order to determine directly the paths in an optimal solution.     

Covering the sphere by equal zones

A zone of half-width w on the unit sphere S² in Euclidean 3-space is the parallel domain of radius w of a great circle. L. Fejes Tóth raised the following question in [6]: what is the minimal w_n such that one can cover S² with n zones of half-width w_n? This question can be considered as a spherical relative of the famous plank problem of Tarski. We prove lower bounds for the minimum half-width w_n for all n ≧ 5.     

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.     

A generalized moment problem for self-adjoint operators

Let the sequence {λ _i } (i≧0) satisfy condition (1.1) and let {A _n} (n≧0) be a sequence of bounded self-adjoint operators over a complex Hilbert spaceH. We give a necessary and sufficient condition in order that {A _n} (n≧0) should possess the representation (1.2).     

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.     

Ergodic theorems for coset spaces

We study in this paper the validity of the Mean Ergodic Theorem along left Følner sequences in a countable amenable group G. Although the Weak Ergodic Theorem always holds along any left Følner sequence in G, we provide examples where the Mean Ergodic Theorem fails in quite dramatic ways. On the other hand, if G does not admit any ICC quotients, e.g., if G is virtually nilpotent, then the Mean Ergodic Theorem holds along any left Følner sequence. In the case when a unitary representation of a countable amenable group is induced from a unitary representation of a “sufficiently thin” subgroup, we show that the Mean Ergodic Theorem holds for the induced representation along any left Følner sequence. Furthermore, we show that every countable (infinite) amenable group L embeds into a countable (not necessarily amenable) group G which admits a unitary representation with the property that for any left Følner sequence (F_n) in L, there exists a sequence (s_n) in G such that the Mean (but not the Weak) Ergodic Theorem fails in a rather strong sense along the (right-translated) sequence (F_ns_n) in G. Finally, we provide examples of countable (not necessarily amenable) groups G with proper, infinite-index subgroups H, so that the Pointwise Ergodic Theorem holds for averages along any strictly increasing and nested sequence of finite subsets of the coset G/H.     

On the rate of decay of concentration functions of <Emphasis Type="Italic">n</Emphasis>-fold convolutions of probability distributions

Concentration functions of n-fold convolutions of probability distributions is shown to exhibit the following behavior. Let φ(n) be an arbitrary sequence tending to infinity as n tends to infinity, and ψ(x) be an arbitrary function tending to infinity as x tends to infinity. Then there exists a probability distribution F of a random variable X such that the mathematical expectation E _ψ(|X|) is infinite and, moreover, the upper limit of the sequence \(\sqrt n \phi \left( n \right)Q_n\) is equal to infinity, where Q _n is the maximal atom of the n-fold convolution of distribution F. Thus, no infinity conditions imposed on the moments can force the concentration functions of n-fold convolutions decay essentially faster than o(n ^?1/2).     

Asymptotic expansions of periodic solutions of ordinary differential equations with large high-frequency terms

We consider the problem on the periodic solutions of a system of ordinary differential equations of arbitrary order n containing terms oscillating at a frequency ω ? 1 with coefficients of the order of ω ^n/2. For this problem, we construct the averaged (limit) problem and justify the averaging method as well as another efficient algorithm for constructing the complete asymptotics of the solution.