A numerical method for solving the Dirichlet problem for the wave equation

In this paper we present a numerical method for solving the Dirichlet problem for a two-dimensional wave equation. We analyze the ill-posedness of the problem and construct a regularization algorithm. Using the Fourier series expansion with respect to one variable, we reduce the problem to a sequence of Dirichlet problems for one-dimensional wave equations. The first stage of regularization consists in selecting a finite number of problems from this sequence. Each of the selected Dirichlet problems is formulated as an inverse problem Aq = f with respect to a direct (well-posed) problem. We derive formulas for singular values of the operator A in the case of constant coefficients and analyze their behavior to judge the degree of ill-posedness of the corresponding problem. The problem Aq = f on a uniform grid is reduced to a system of linear algebraic equations A _ll q = F. Using the singular value decomposition, we find singular values of the matrix A _ll and develop a numerical algorithm for constructing the r-solution of the original problem. This algorithm was tested on a discrete problem with relatively small number of grid nodes. To improve the calculated r-solution, we applied optimization but observed no noticeable changes. The results of computational experiments are illustrated.     

A uniqueness theorem in the inverse problem for the integrodifferential electrodynamics equations

Under study is the problem of finding the kernel and the index of dielectric permeability for the system of integrodifferential electrodynamics equations with wave dispersion. We consider a direct problem in which the external pulse current is a dipole located at a point y on the boundary ?B of the unit ball B. The point y runs over the whole boundary and is a parameter of the problem. The information available about the solution to the direct problem is the trace on ?B of the solution to the Cauchy problem given for the times close to the time when a wave from the dipole source arrives at a point x. The main result of the article consists in obtaining some theorems related to the uniqueness problems for a solution to the inverse problem.     

Minimum monopoly in regular and tree graphs

In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set S⊆V, such that, for each u∈V, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.     

Intersection theorems under dimension constraints

In Ahlswede et al. [Discrete Math. 273(1-3) (2003) 9-21] we posed a series of extremal (set system) problems under dimension constraints. In the present paper, we study one of them: the intersection problem. The geometrical formulation of our problem is as follows. Given integers 0?t, k?n determine or estimate the maximum number of (0,1)-vectors in a k-dimensional subspace of the Euclidean n-space Rⁿ, such that the inner product (“intersection”) of any two is at least t. Also we are interested in the restricted (or the uniform) case of the problem; namely, the problem considered for the (0,1)-vectors of the same weight ω.The paper consists of two parts, which concern similar questions but are essentially independent with respect to the methods used.In Part I, we consider the unrestricted case of the problem. Surprisingly, in this case the problem can be reduced to a weighted version of the intersection problem for systems of finite sets. A general conjecture for this problem is proved for the cases mentioned in Ahlswede et al. [Discrete Math. 273(1-3) (2003) 9-21]. We also consider a diametric problem under dimension constraint.In Part II, we study the restricted case and solve the problem for t=1 and k<2ω, and also for any fixed 1?t?ω and k large.     

A new method of solving nonlinear mathematical programming problems involving r-invex functions

A new approach to a solution of a nonlinear constrained mathematical programming problem involving r-invex functions with respect to the same function η is introduced. An η-approximated problem associated with an original nonlinear mathematical programming problem is presented that involves η-approximated functions constituting the original problem. The equivalence between optima points for the original mathematical programming problem and its η-approximated optimization problem is established under r-invexity assumption.     

On the forbidden induced subgraph sandwich problem

We consider the sandwich problem, a generalization of the recognition problem introduced by Golumbic et al. (1995) [15], with respect to classes of graphs defined by excluding induced subgraphs. We prove that the sandwich problem corresponding to excluding a chordless cycle of fixed length k is NP-complete. We prove that the sandwich problem corresponding to excluding K_r?e for fixed r is polynomial. We prove that the sandwich problem corresponding to 3PC(⋅,⋅)-free graphs is NP-complete. These complexity results are related to the classification of a long-standing open problem: the sandwich problem corresponding to perfect graphs.     

The two-machine no-wait general and proportionate open shop makespan problem

We consider the two-machine no-wait open shop minimum makespan problem in which the determination of an optimal solution requires an optimal pairing of the jobs followed by the optimal sequencing of the job pairs. We show that the required enumeration can be curtailed by reducing the pair sequencing problem for a given pair set to a traveling salesman problem which is equivalent to a two-machine no-wait flow shop problem solvable in O(n log n) time. We then propose an optimal O(n log n) algorithm for the proportionate problem with equal machine speeds in which each job has the same processing time on both machines. We show that our O(n log n) algorithm also applies to the more general proportionate problem with equal machine speeds and machine-specific setup times. We also analyze the proportionate problem with unequal machine speeds and conclude that the required enumeration can be further curtailed (compared to the problem with arbitrary job processing times) by eliminating certain job pairs from consideration.     

The complexity of the weight problem for permutation and matrix groups

Given a metric d on a permutation group G, the corresponding weight problem is to decide whether there exists an element π∈G such that d(π,e)=k, for some given value k. Here we show that this problem is NP-complete for many well-known metrics. An analogous problem in matrix groups, eigenvalue-free problem, and two related problems in permutation groups, the maximum and minimum weight problems, are also investigated in this paper.     

A branch-and-bound method for the minimum k−enclosing ball problem

The minimum k-enclosing ball problem seeks the ball with smallest radius that contains at least k of m given points. This problem is NP-hard. We present a branch-and-bound algorithm on the tree of the subsets of k points to solve this problem. Our method is able to solve the problem exactly in a short amount of time for small and medium sized datasets.     

Approximation algorithms for constrained generalized tree alignment problem

In generalized tree alignment problem, we are given a set S of k biologically related sequences and we are interested in a minimum cost evolutionary tree for S. In many instances of this problem partial phylogenetic tree for S is known. In such instances, we would like to make use of this knowledge to restrict the tree topologies that we consider and construct a biologically relevant minimum cost evolutionary tree. So, we propose the following natural generalization of the generalized tree alignment problem, a problem known to be MAX-SNP Hard, stated as follows:

Constrained Generalized Tree Alignment Problem [S. Divakaran, Algorithms and heuristics for constrained generalized alignment problem, DIMACS Technical Report 2007-21, 2007]: Given a set S of k related sequences and a phylogenetic forest comprising of node-disjoint phylogenetic trees that specify the topological constraints that an evolutionary tree of S needs to satisfy, construct a minimum cost evolutionary tree for S.

In this paper, we present constant approximation algorithms for the constrained generalized tree alignment problem. For the generalized tree alignment problem, a special case of this problem, our algorithms provide a guaranteed error bound of 2−2/k.     

‘Multidimensional’ extensions and a nested dual approach for the m-median problem

A general framework for modeling median type locational decisions, where (i) travel costs and demands may be stochastic, (ii) multiple services or commodities need to be considered, and/or (iii) multiple median type objectives might exist, is presented—using the concept of “multidimensional networks”. The classical m-median problem, the stochastic m-median problem, the multicommodity m-median problem and and multiobjective m-median problem are defined within this framework.By an appropriate transformation of variables, the multidimensional m-median problem simplifies to the classical m-median problem but with a K-fold increase in the number of nodes, where K is the number of dimensions of the network. A nested dual approach to solve the resulting classical m-median problem, that uses Erlenkotter's facility location scheme as a subroutine, is presented. Computational results indicate that the procedure may perhaps be the best available one to solve the m-median problem exactly.     

A global in time existence and uniqueness result for an integrodifferential hyperbolic inverse problem with memory effect

We consider an inverse problem for a one-dimensional integrodifferential hyperbolic system, which comes from a simplified model of thermoelasticity. This inverse problem aims to identify the displacement u, the temperature η and the memory kernel k simultaneously from the weighted measurement data of temperature. By using the fixed point theorem in suitable Sobolev spaces, the global in time existence and uniqueness results of this inverse problem are obtained. Moreover, we prove that the solution to this inverse problem depends continuously on the noisy data in suitable Sobolev spaces. For this nonlinear inverse problem, our theoretical results guarantee the solvability for the proposed physical model and the well-posedness for small measurement time τ, which is quite different from general inverse problems.     

On a non-homogeneous eigenvalue problem involving a potential: An Orlicz–Sobolev space setting

In this paper we study a non-homogeneous eigenvalue problem involving variable growth conditions and a potential V. The problem is analyzed in the context of Orlicz–Sobolev spaces. Connected with this problem we also study the optimization problem for the particular eigenvalue given by the infimum of the Rayleigh quotient associated to the problem with respect to the potential V when V lies in a bounded, closed and convex subset of a certain variable exponent Lebesgue space.     

The even Orlicz Minkowski problem

The classical Minkowski problem leads to the Lp Minkowski problem and now to the Orlicz Minkowski problem. Existence is demonstrated for the even Orlicz Minkowski problem. A byproduct is a new approach to the solution of the classical Minkowski problem.     

On the complexity of a family of generalized matching problems

We consider a family of generalized matching problems called k-feasible matching (k-RM) problems, where k? {1,2,3,…} ∪ {∞}. We show each k-FM problem to be NP-complete even for very restricted cases. We develop a dynamic programming algorithm that solves in polynomial time the k-FM problem for graphs with width bounded by 2k. We also show that for any subset S of {1,2,…} ∪ {∞}, there is a set D of problem instances such that for k in S the k-FM problem is NP-complete on D, while for k not in S the k-FM problem is polynomially solvable on D.     

Inverse 1-median problem on trees under weighted Hamming distance

The inverse 1-median problem consists in modifying the weights of the customers at minimum cost such that a prespecified supplier becomes the 1-median of modified location problem. A linear time algorithm is first proposed for the inverse problem under weighted l _?? norm. Then two polynomial time algorithms with time complexities O(n log n) and O(n) are given for the problem under weighted bottleneck-Hamming distance, where n is the number of vertices. Finally, the problem under weighted sum-Hamming distance is shown to be equivalent to a 0-1 knapsack problem, and hence is ${\mathcal{NP}}$ -hard.     

A fast algorithm for multiplying min-sum permutations

The present article considers the problem for determining, for given two permutations over indices from 1 to n, the permutation whose distribution matrix is identical to the min-sum product of the distribution matrices of the given permutations. This problem has several applications in computing the similarity between strings. The fastest known algorithm to date for solving this problem executes in O(n^1.5) time, or very recently, in O(nlogn) time. The present article independently proposes another O(nlogn)-time algorithm for the same problem, which can also be used to partially solve the problem efficiently with respect to time in the sense that, for given indices g and i with 1≤g<i≤n+1, the proposed algorithm outputs the values R(h) for all indices h with g≤h<i in O(n+(i−g)log(i−g)) time, where R is the solution of the problem.     

A neural network approach to facility layout problems

A near-optimum parallel algorithm for solving facility layout problems is presented in this paper where the problem is NP-complete. The facility layout problem is one of the most fundamental quadratic assignment problems in Operations Research. The goal of the problem is to locate N facilities on an N-square (location) array so as to minimize the total cost. The proposed system is composed of N × N neurons based on an artificial two-dimensional maximum neural network for an N-facility layout problem. Our algorithm has given improved solutions for several benchmark problems over the best existing algorithms.     

The Cauchy problem in Sobolev spaces for Dirac operators

In this paper we consider the Cauchy problem as a typical example of ill-posed boundary-value problems. We obtain the necessary and (separately) sufficient conditions for the solvability of the Cauchy problem for a Dirac operator A in Sobolev spaces in a bounded domain D ? ? ⁿ with a piecewise smooth boundary. Namely, we reduce the Cauchy problem for the Dirac operator to the problem of harmonic extension from a smaller domain to a larger one. Moreover, along with the solvability conditions for the problem, using bases with double orthogonality, we construct a Carleman formula for recovering a function u in a Sobolev space H ^s (D), s ∈ ?, from its values on Γ and values Au in D, where Γ is an open connected subset of the boundary ?D. It is worth pointing out that we impose no assumptions about geometric properties of the domain D, except for its connectedness.     

A SURVEY OF THE ADDITIVE EIGENVALUE PROBLEM (WITH APPENDIX BY M. KAPOVICH)

The classical Hermitian eigenvalue problem addresses the following question: What are the possible eigenvalues of the sum A + B of two Hermitian matrices A and B, provided we fix the eigenvalues of A and B. A systematic study of this problem was initiated by H. Weyl (1912). By virtue of contributions from a long list of mathematicians, notably Weyl (1912), Horn (1962), Klyachko (1998) and Knutson–Tao (1999), the problem is finally settled. The solution asserts that the eigenvalues of A + B are given in terms of certain system of linear inequalities in the eigenvalues of A and B. These inequalities (called the Hom inequalities) are given explicitly in terms of certain triples of Schubert classes in the singular cohomology of Grassmannians and the standard cup product. Belkale (2001) gave a smaller set of inequalities for the problem in this case (which was shown to be optimal by Knutson–Tao–Woodward). The Hermitian eigenvalue problem has been extended by Berenstein–Sjamaar (2000) and Kapovich–Leeb–Millson (2009) for any semisimple complex algebraic group G. Their solution is again in terms of a system of linear inequalities obtained from certain triples of Schubert classes in the singular cohomology of the partial ag varieties G/P (P being a maximal parabolic subgroup) and the standard cup product. However, their solution is far from being optimal. In a joint work with P. Belkale, we define a deformation of the cup product in the cohomology of G/P and use this new product to generate our system of inequalities which solves the problem for any G optimally (as shown by Ressayre). This article is a survey (with more or less complete proofs) of this additive eigenvalue problem. The eigenvalue problem is equivalent to the saturated tensor product problem. We also give an extension of the saturated tensor product problem to the saturated restriction problem for any pair G ? ? of connected reductive algebraic groups. In the appendix by M. Kapovich, a connection between metric geometry and the representation theory of complex semisimple algebraic groups is explained. The connection runs through the theory of buildings. This connection is exploited to give a uniform (though not optimal) saturation factor for any G.