Minimum variance quadratic unbiased estimators as a tool to identify compound normal distributions

We derive the minimum variance quadratic unbiased estimator (MIVQUE) of the variance of the components of a random vector having a compound normal distribution (CND). We show that the MIVQUE converges in probability to a random variable whose distribution is essentially the mixing distribution characterising the CND. This fact is very important, because the MIVQUE allows us to make out the signature of a particular CND, and notably allows us to check if an hypothesis of normality for multivariate observations y₁,…,y_M is plausible.     

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.     

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.     

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.     

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.     

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.     

On a boundary value problem for a higher-order elliptic equation

For an elliptic 2lth-order equation with constant (and only leading) real coefficients, we consider the boundary value problem in which the (k _j ? 1)st normal derivatives, j = 1,..., l, are specified, where 1 ≤ k ₁ < ... < k _l . If k _j = j, then it becomes the Dirichlet problem; and if k _j = j + 1, then it becomes the Neumann problem. We obtain a sufficient condition for this problem to be Fredholm and present a formula for the index of the 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.     

Clustering and domination in perfect graphs

A k-cluster in a graph is an induced subgraph on k vertices which maximizes the number of edges. Both the k-cluster problem and the k-dominating set problem are NP-complete for graphs in general. In this paper we investigate the complexity status of these problems on various sub-classes of perfect graphs. In particular, we examine comparability graphs, chordal graphs, bipartite graphs, split graphs, cographs and κ-trees. For example, it is shown that the k-cluster problem is NP-complete for both bipartite and chordal graphs and the independent k-dominating set problem is NP-complete for bipartite graphs. Furthermore, where the k-cluster problem is polynomial we study the weighted and connected versions as well. Similarly we also look at the minimum k-dominating set problem on families which have polynomial k-dominating set algorithms.     

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.     

Degree bounded matroids and submodular flows

We consider two related problems, the Minimum Bounded Degree Matroid Basis problem and the Minimum Bounded Degree Submodular Flow problem. The first problem is a generalization of the Minimum Bounded Degree Spanning Tree problem: We are given a matroid and a hypergraph on its ground set with lower and upper bounds f(e)≤g(e) for each hyperedge e. The task is to find a minimum cost basis which contains at least f(e) and at most g(e) elements from each hyperedge e. In the second problem we have a submodular flow problem, a lower bound f(v) and an upper bound g(v) for each node v, and the task is to find a minimum cost 0–1 submodular flow with the additional constraint that the sum of the incoming and outgoing flow at each node v is between f(v) and g(v). Both of these problems are NP-hard (even the feasibility problems are NP-complete), but we show that they can be approximated in the following sense. Let opt be the value of the optimal solution. For the first problem we give an algorithm that finds a basis B of cost no more than opt such that f(e)?2Δ+1≤|B∩e|≤g(e)+2Δ?1 for every hyperedge e, where Δ is the maximum degree of the hypergraph. If there are only upper bounds (or only lower bounds), then the violation can be decreased to Δ?1. For the second problem we can find a 0–1 submodular flow of cost at most opt where the sum of the incoming and outgoing flow at each node v is between f(v)?1 and g(v)+1. These results can be applied to obtain approximation algorithms for several combinatorial optimization problems with degree constraints, including the Minimum Crossing Spanning Tree problem, the Minimum Bounded Degree Spanning Tree Union problem, the Minimum Bounded Degree Directed Cut Cover problem, and the Minimum Bounded Degree Graph Orientation problem.     

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.     

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.     

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

Retractions onto series-parallel posets

The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study this problem for finite series-parallel posets P. We present equivalent combinatorial, algebraic, and topological charaterisations of posets for which the problem is tractable, and, for such a poset P, we describe posets admitting a retraction onto P.     

R-domination on block graphs

The k-domination problem is to select a minimum cardinality vertex set D of a graph G such that every vertex of G is within distance k from some vertex of D. We consider a generalization of the k-domination problem, called the R-domination problem. A linear algorithm is presented that solves this problem for block graphs. Our algorithm is a generalization of Slater's algorithm [12], which is applicable for forest graphs.     

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

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.     

Coloring half-planes and bottomless rectangles

We prove lower and upper bounds for the chromatic number of certain hypergraphs defined by geometric regions. This problem has close relations to conflict-free colorings. One of the most interesting type of regions to consider for this problem is that of the axis-parallel rectangles. We completely solve the problem for a special case of them, for bottomless rectangles. We also give an almost complete answer for half-planes and pose several open problems. Moreover, we give efficient coloring algorithms.