An inverse eigenvalue problem and an associated approximation problem for generalized K-centrohermitian matrices

A partially described inverse eigenvalue problem and an associated optimal approximation problem for generalized K-centrohermitian matrices are considered. It is shown under which conditions the inverse eigenproblem has a solution. An expression of its general solution is given. In case a solution of the inverse eigenproblem exists, the optimal approximation problem can be solved. The formula of its unique solution is given.     

An improved non-local boundary value problem method for a cauchy problem of the Laplace equation

In this paper, we propose an improved non-local boundary value problem method to solve a Cauchy problem for the Laplace equation. It is known that the Cauchy problem for the Laplace equation is severely ill-posed, i.e., the solution does not depend continuously on the given Cauchy data. Convergence estimates for the regularized solutions are obtained under a-priori bound assumptions for the exact solution. Some numerical results are given to show the effectiveness of the proposed method.     

Inverse minimum flow problem

In this paper we consider the inverse minimum flow (ImF) problem, where lower and upper bounds for the flow must be changed as little as possible so that a given feasible flow becomes a minimum flow. A linear time and space method to decide if the problem has solution is presented. Strongly and weakly polynomial algorithms for solving the ImF problem are proposed. Some particular cases are studied and a numerical example is given.     

Zolotarev's conformal mapping and Chebotarev's problem

Consider the Chebotarev problem of finding a continuum S in the complex plane including some given points such that the logarithmic capacity of S is minimal. In this paper, we give a complete solution of this problem for the case of three given points with the help of Zolotarev's conformal mapping using Jacobian elliptic and theta functions. Moreover, for four given points, some special cases can be treated.     

A Dirichlet problem for polyharmonic functions

In this article, the Dirichlet problem of polyharmonic functions is considered. As well the explicit expression of the unique solution to the simple Dirichlet problem for polyharmonic functions is obtained by using the decomposition of polyharmonic functions and turning the problem into an equivalent Riemann boundary value problem for polyanalytic functions, as the approach to find the kernel functions of the solution for the general Dirichlet problem is given. Project supported by NNSF of China.     

The string merging problem

The string merging problem is to determine a merged string from a given set of strings. The distinguishing property of a solution is that the total cost of editing all of the given strings into this solution is minimal. Necessary and sufficient conditions are presented for the case where this solution matches the solution to the string-to-string correction problem. A special case where deletion is the only allowed edition operation is shown to have the longest common subsequence of the strings as its solution.This research was supported by the U.S. Army Research Office.     

A modified method for a non-standard inverse heat conduction problem

A non-standard inverse heat conduction problem is considered. Data are given along the line x = 1 and the solution at x = 0 is sought. The problem is ill-posed in the sense that the solution (if it exists) does not depend continuously on the data. In order to solve the problem numerically it is necessary to employ some regularization method. In this paper, we study a modification of the equation, where a fourth-order mixed derivative term is added. Error estimates for this equation are given, which show that the solution of the modified equation is an approximation of the heat equation. A numerical implementation is considered and a simple example is given. Some numerical results show the usefulness of the modified method.     

Solving the shortest path tour problem

In this paper, we study the shortest path tour problem in which a shortest path from a given origin node to a given destination node must be found in a directed graph with non-negative arc lengths. Such path needs to cross a sequence of node subsets that are given in a fixed order. The subsets are disjoint and may be different-sized. A polynomial-time reduction of the problem to a classical shortest path problem over a modified digraph is described and two solution methods based on the above reduction and dynamic programming, respectively, are proposed and compared with the state-of-the-art solving procedure. The proposed methods are tested on existing datasets for this problem and on a large class of new benchmark instances. The computational experience shows that both the proposed methods exhibit a consistent improved performance in terms of computational time with respect to the existing solution method.     

Single machine stochastic JIT scheduling problem subject to machine breakdowns

In this paper we research the single machine stochastic JIT scheduling problem subject to the machine breakdowns for preemptive-resume and preemptive-repeat.The objective function of the problem is the sum of squared deviations of the job-expected completion times from the due date.For preemptive-resume,we show that the optimal sequence of the SSDE problem is V-shaped with respect to expected processing times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.We discuss the difference between the SSDE problem and the ESSD problem and show that the optimal solution of the SSDE problem is a good approximate optimal solution of the ESSD problem,and the optimal solution of the SSDE problem is an optimal solution of the ESSD problem under some conditions.For preemptive-repeat,the stochastic JIT scheduling problem has not been solved since the variances of the completion times cannot be computed.We replace the ESSD problem by the SSDE problem.We show that the optimal sequence of the SSDE problem is V-shaped with respect to the expected occupying times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.A new thought is advanced for the research of the preemptive-repeat stochastic JIT scheduling problem.     

On Oka’s extra-zero problem and examples

After the solution of Cousin II problem by Oka III in 1939, he thought an extra-zero problem in 1945 (his posthumous paper) asking if it is possible to solve an arbitrarily given Cousin II problem adding some extra-zeros whose support is disjoint from the given one. By the secondly named author, some special case was affirmatively confirmed in dimension two and a counter-example in dimension three or more was given. The purpose of the present paper is to give a complete solution of this problem with examples and some new questions.     

Solving fixed charge transportation problem with interval parameters

In the present paper the fixed charge transportation problem under uncertainty, particularly when parameters are given in interval forms, is formulated. In this case it is assumed that both cost and constraint parameters are arrived in interval numbers. Considering two different order relations for interval numbers, two solution procedures are developed in order to obtain an optimal solution for interval fixed charge transportation problem (IFCTP). In addition, the two order relations are compared to give a better comprehension of their differences. Furthermore, numerical examples are provided to illustrate each of solution procedures.     

Fuzzy relational equations and the inverse problem

The inverse problem concerned with fuzzy relations is investigated. The conditions for the existence of a solution are shown and an analytical solution is given. A method for the improvement of the solution is proposed.     

Borsuk's problem

The Borsuk number of a bounded set F is the smallest natural number k such that F can be represented as a union of k sets, the diameter of each of which is less than diam F. In this paper we solve the problem of finding the Borsuk number of any bounded set in an arbitrary two-dimensional normed space (the solution is given in terms of the enlargement of a set to a figure of constant width). We indicate spaces for which the solution of Borsuk's problem has the same form as in the Euclidean plane.Translated from Matematicheskie Zametki, Vol. 22, No. 5, pp. 621–631, November, 1977.     

Boundary value problem of a third-order mixed type differential-difference equation

In this paper, the existence and uniqueness of the solution for the boundary value problem of a third order mixed differential-difference equation is given by using Schauder's fixed point theorem, and an approximate solution is given by using the Picard's iterative methods.     

Heuristic algorithms for the multiple-choice multidimensional knapsack problem

In this paper, we propose several heuristics for approximately solving the multiple-choice multidimensional knapsack problem (noted MMKP), an NP-Hard combinatorial optimization problem. The first algorithm is a constructive approach used especially for constructing an initial feasible solution for the problem. The second approach is applied in order to improve the quality of the initial solution. Finally, we introduce the main algorithm, which starts by applying the first approach and tries to produce a better solution to the MMKP. The last approach can be viewed as a two-stage procedure: (i) the first stage is applied in order to penalize a chosen feasible solution and, (ii) the second stage is used in order to normalize and to improve the solution given by the firs stage. The performance of the proposed approaches has been evaluated based problem instances extracted from the literature. Encouraging results have been obtained.     

Spectral regularization method for solving a time-fractional inverse diffusion problem

In this paper, we consider an inverse problem for a time-fractional diffusion equation with one-dimensional semi-infinite domain. The temperature and heat flux are sought from a measured temperature history at a fixed location inside the body. We show that such problem is severely ill-posed and further apply a spectral regularization method to solve it based on the solution given by the Fourier method. Convergence estimates are presented under a priori bound assumptions for the exact solution. Finally, numerical examples are given to show that the proposed numerical method is effective.     

Modified regularization method for the Cauchy problem of the Helmholtz equation

In this paper, the Cauchy problem for the Helmholtz equation is investigated. It is known that such problem is severely ill-posed. We propose a modified regularization method to solve it based on the solution given by the method of separation of variables. Convergence estimates are presented under two different a-priori bounded assumptions for the exact solution. Finally, numerical examples are given to show the effectiveness of the proposed numerical method.     

The Riemann-Hilbert problem for certain poly domains and its connection to the Riemann problem

The Riemann-Hilbert problem is studied for holomorphic functions in higher dimensional poly domains and the explicit constructive solution is given. The connection between the Riemann problem and the Riemann-Hilbert problem for poly domains is presented and proven. Contrary to earlier studies, our results provide explicit solutions and are not attached to any artificial assumptions.     

HGAH矩阵的逆特征值问题

In this paper, the inverse eigenvalue problem of Hermitian generalized anti-Hamihonian matrices and relevant optimal approximate problem are considered. The necessary and sufficient conditions of the solvability for inverse eigenvalue problem and an expression of the general solution of the problem are derived. The solution of the relevant optimal approximate problem is given.     

The expropriation location problem

In this paper, we consider the location of a new obnoxious facility that serves only a certain proportion of the demand. Each demand point can be bought by the developer at a given price. An expropriation budget is given. Demand points closest to the facility are expropriated within the given budget. The objective is to maximize the distance to the closest point not expropriated. The problem is formulated and polynomial algorithms are proposed for its solution both on the plane and on a network.