On the complexity of the dominating induced matching problem in hereditary classes of graphs

The dominating induced matching problem, also known as efficient edge domination, is the problem of determining whether a graph has an induced matching that dominates every edge of the graph. This problem is known to be NP-complete. We study the computational complexity of the problem in special graph classes. In the present paper, we identify a critical class for this problem (i.e., a class lying on a “boundary” separating difficult instances of the problem from polynomially solvable ones) and derive a number of polynomial-time results. In particular, we develop polynomial-time algorithms to solve the problem for claw-free graphs and convex graphs.     

The problem of harmonic analysis on the infinite-dimensional unitary group

The goal of harmonic analysis on a (noncommutative) group is to decompose the most “natural” unitary representations of this group (like the regular representation) on irreducible ones. The infinite-dimensional unitary group U(∞) is one of the basic examples of “big” groups whose irreducible representations depend on infinitely many parameters. Our aim is to explain what the harmonic analysis on U(∞) consists of.We deal with unitary representations of a reasonable class, which are in 1-1 correspondence with characters (central, positive definite, normalized functions on U(∞)). The decomposition of any representation of this class is described by a probability measure (called spectral measure) on the space of indecomposable characters. The indecomposable characters were found by Dan Voiculescu in 1976.The main result of the present paper consists in explicitly constructing a 4-parameter family of “natural” representations and computing their characters. We view these representations as a substitute of the nonexisting regular representation of U(∞). We state the problem of harmonic analysis on U(∞) as the problem of computing the spectral measures for these “natural” representations. A solution to this problem is given in the next paper (Harmonic analysis on the infinite-dimensional unitary group and determinantal point processes, math/0109194, to appear in Ann. Math.), joint with Alexei Borodin.We also prove a few auxiliary general results. In particular, it is proved that the spectral measure of any character of U(∞) can be approximated by a sequence of (discrete) spectral measures for the restrictions of the character to the compact unitary groups U(N). This fact is a starting point for computing spectral measures.     

Accelerated algorithm for pattern detection in logical analysis of data

Sets of “positive” and “negative” points (observations) in n-dimensional discrete space given along with their non-negative integer multiplicities are analyzed from the perspective of the Logical Analysis of Data (LAD). A set of observations satisfying upper and/or lower bounds imposed on certain components is called a positive pattern if it contains some positive observations and no negative one. The number of variables on which such restrictions are imposed is called the degree of the pattern. A total polynomial algorithm is proposed for the enumeration of all patterns of limited degree, and special efficient variants of it for the enumeration of all patterns with certain “sign” and “coverage” requirements are presented and evaluated on a publicly available collection of benchmark datasets.     

The economics of social computing: Some preliminary findings on healthcare organizations

Large-scale organizations have used social computing platforms for various purposes. This research focuses on how hospitals utilize these platforms to attract potential customers (which represents the “extensivity” of a social computing platform) and generate interests in specific topics (which represents the “intensivity” of a platform). Specifically, we examine the effects of size of a hospital (or “size”) and the time that the social computing platform has been in existence (or “time”) on extensivity and intensivity. Our findings show that time is a significant variable on both dimensions; whereas size affects intensivity under certain conditions. We discuss the implications of these findings, and set the stage for future research.     

A dual simplex-based method for determination of the right and left returns to scale in DEA

This study reviews the concept of the “right” and the “left” returns to scale (RTS) in data envelopment analysis (DEA), and a dual simplex-based method, for determining these two notions in RTS, is proposed, which has computational advantages as compared to the customary method.     

Long distance wave computation using nonlinear solitary waves

A recently developed method is described to propagate short wave equation pulses over indefinite distances and through regions of varying indices of refraction, including multiple reflections. The method, “Wave Confinement”, utilizes a newly developed nonlinear partial differential equation (pde) that propagates basis functions according to the wave equation. These basis functions are generated as stable solitary waves where the discretized equation can be solved without any numerical dissipation. The method can also be used to solve for harmonic waves in the high frequency (Eikonal) limit, including multiple arrivals. The solution involves discretizing the wave equation on a uniform Eulerian grid and adding a simple nonlinear “Confinement” term. This term does not change the amplitude (integrated through each point on the pulse surface) or the propagation velocity, or arrival time, and yet results in capturing the waves as thin surfaces that propagate as thin nonlinear solitary waves and remain ∼2-3 grid cells in thickness indefinitely with no numerical spreading. A new feature described in this paper involves computing scattering of short pulses from complex objects such as complete aircraft. A simple “immersed surface” approach is used, that utilizes the same uniform grid as the propagation and avoids complex, body fitted or adaptive grid schemes.The new method should be useful in areas of wave propagation, from radar scattering and long distance communications to cell phone transmission.     

Analysis of stochastic dual dynamic programming method

In this paper we discuss statistical properties and convergence of the Stochastic Dual Dynamic Programming (SDDP) method applied to multistage linear stochastic programming problems. We assume that the underline data process is stagewise independent and consider the framework where at first a random sample from the original (true) distribution is generated and consequently the SDDP algorithm is applied to the constructed Sample Average Approximation (SAA) problem. Then we proceed to analysis of the SDDP solutions of the SAA problem and their relations to solutions of the “true” problem. Finally we discuss an extension of the SDDP method to a risk averse formulation of multistage stochastic programs. We argue that the computational complexity of the corresponding SDDP algorithm is almost the same as in the risk neutral case.     

The inequality-satisfiability problem

We define a generalization of the satisfiability problem (SAT) where each “clause” is an or-list of inequalities in n variables. This problem is NP-complete even when containing only two inequalities per “clause”, but solvable in polynomial time when either the number of variables or the number of “clauses” is fixed.     

AIR Tools — A MATLAB package of algebraic iterative reconstruction methods

We present a MATLAB package with implementations of several algebraic iterative reconstruction methods for discretizations of inverse problems. These so-called row action methods rely on semi-convergence for achieving the necessary regularization of the problem. Two classes of methods are implemented: Algebraic Reconstruction Techniques (ART) and Simultaneous Iterative Reconstruction Techniques (SIRT). In addition we provide a few simplified test problems from medical and seismic tomography. For each iterative method, a number of strategies are available for choosing the relaxation parameter and the stopping rule. The relaxation parameter can be fixed, or chosen adaptively in each iteration; in the former case we provide a new “training” algorithm that finds the optimal parameter for a given test problem. The stopping rules provided are the discrepancy principle, the monotone error rule, and the NCP criterion; for the first two methods “training” can be used to find the optimal discrepancy parameter.     

The Carlitz shtuka

Recently we have used the Carlitz exponential map to define a finitely generated submodule of the Carlitz module having the right properties to be a function field analogue of the group of units in a number field. Similarly, we constructed a finite module analogous to the class group of a number field. In this short note more algebraic constructions of these “unit” and “class” modules are given and they are related to Ext modules in the category of shtukas.     

Modified algorithms for the minimum volume enclosing axis-aligned ellipsoid problem

Consider the problem of computing a (1+?)-approximation to the minimum volume axis-aligned ellipsoid (MVAE) enclosing a set of m points in Rⁿ. We first provide an extension and improvement to algorithm proposed in Kumar and Y?ld?r?m (2008) [5] (the KY algorithm) for the MVAE problem. The main challenge of the MVAE problem is that there is no closed form solution in the line search step (beta). Therefore, the KY algorithm proposed a certain choice of beta that leads to their complexity and core set results in solving the MVAE problem. We further analyze the line search step to derive a new beta, relying on an analysis of up to the fourth order derivative. This choice of beta leads to the improved complexity and core set results. The second modification is given by incorporating “away steps” into the first one at each iteration, which obtains the same complexity and core set results as the first one. In addition, since the second modification uses the idea of “dropping points”, it has the potential to compute smaller core sets in practice. Some numerical results are given to show the efficiency of the modified algorithms.     

The efficient solution of the (quietly constrained) noisy, linear regulator problem

In a previous paper we gave a new, natural extension of the calculus of variations/optimal control theory to a (strong) stochastic setting. We now extend the theory of this most fundamental chapter of optimal control in several directions. Most importantly we present a new method of stochastic control, adding Brownian motion which makes the problem “noisy.” Secondly, we show how to obtain efficient solutions: direct stochastic integration for simpler problems and/or efficient and accurate numerical methods with a global a priori error of O(h3/2) for more complex problems. Finally, we include “quiet” constraints, i.e. deterministic relationships between the state and control variables. Our theory and results can be immediately restricted to the non “noisy” (deterministic) case yielding efficient, numerical solution techniques and an a priori error of O(h²). In this event we obtain the most efficient method of solving the (constrained) classical Linear Regulator Problem. Our methods are different from the standard theory of stochastic control. In some cases the solutions coincide or at least are closely related. However, our methods have many advantages including those mentioned above. In addition, our methods more directly follow the motivation and theory of classical (deterministic) optimization which is perhaps the most important area of physical and engineering science. Our results follow from related ideas in the deterministic theory. Thus, our approximation methods follow by guessing at an algorithm, but the proof of global convergence uses stochastic techniques because our trajectories are not differentiable. Along these lines, a general drift term in the trajectory equation is properly viewed as an added constraint and extends ideas given in the deterministic case by the first author.     

Using Noonan–Zeilberger Functional Equations to enumerate (in polynomial time!) generalized Wilf classes

One of the most challenging problems in enumerative combinatorics is to count Wilf classes, where you are given a pattern, or set of patterns, and you are asked to find a “formula”, or at least an efficient algorithm, that inputs a positive integer n and outputs the number of permutations avoiding that pattern. In 1996, John Noonan and Doron Zeilberger initiated the counting of permutations that have a prescribed, r, say, occurrences of a given pattern. They gave an ingenious method to generate functional equations, alas, with an unbounded number of “catalytic variables”, but then described a clever way, using multivariable calculus, on how to get enumeration schemes. Alas, their method becomes very complicated for r larger than 1. In the present article we describe a far simpler way to squeeze the necessary information, in polynomial time, for increasing patterns of any length and for any number of occurrences r.     

Extension of VIKOR method for decision making problem with interval numbers

The VIKOR method was developed for multi-criteria optimization of complex systems. It determines the compromise ranking list and the compromise solution obtained with the initial (given) weights. This method focuses on ranking and selecting from a set of alternatives in the presence of conflicting criteria. It introduces the multi-criteria ranking index based on the particular measure of “closeness” to the “ideal” solution. The aim of this paper is to extend the VIKOR method for decision making problems with interval number. The extended VIKOR method’s ranking is obtained through comparison of interval numbers and for doing the comparisons between intervals, we introduce α as optimism level of decision maker. Finally, a numerical example illustrates and clarifies the main results developed in this paper.     

Bounds for a multivariate extension of range over standard deviation based on the Mahalanobis distance

The range over standard deviation of a set of univariate data points is given a natural multivariate extension through the Mahalanobis distance. The problem of finding extrema of this multivariate extension of “range over standard deviation” is investigated. The supremum (maximum) is found using Lagrangian methods and an interval is given for the infinimum. The independence of optimizing the Mahalanobis distance and the multivariate extension of range is demonstrated and connections are explored in several examples using an analogue of the “hat” matrix of linear regression.     

How ordinary elimination became Gaussian elimination

Newton, in notes that he would rather not have seen published, described a process for solving simultaneous equations that later authors applied specifically to linear equations. This method — which Euler did not recommend, which Legendre called “ordinary,” and which Gauss called “common” — is now named after Gauss: “Gaussian” elimination. Gauss’s name became associated with elimination through the adoption, by professional computers, of a specialized notation that Gauss devised for his own least-squares calculations. The notation allowed elimination to be viewed as a sequence of arithmetic operations that were repeatedly optimized for hand computing and eventually were described by matrices.     

Some stochastic properties of “semi-magic” and “magic” Markov chains

Gustafson and Styan (Gustafson and Styan, Superstochastic matrices and Magic Markov chains, Linear Algebra Appl. 430 (2009) 2705-2715) examined the mathematical properties of superstochastic matrices, the transition matrices of “magic” Markov chains formed from scaled “magic squares”. This paper explores the main stochastic properties of such chains as well as “semi-magic” chains (with doubly-stochastic transition matrices). Stationary distribution, generalized inverses of Markovian kernels, mean first passage times, variances of the first passage times and expected times to mixing are considered. Some general results are developed, some observations from the chains generated by MATLAB are discussed, some conjectures are presented and some special cases, involving three and four states, are explored in detail.     

Generations and mechanisms of multi-stripe chaotic attractors of fractional order dynamic system

In this paper, the generations of multi-stripe chaotic attractors of fractional order system are considered. The original fractional order chaotic attractors can be turned into a pattern with multiple “parallel” or “ rectangular” stripes by employing certain simple periodic nonlinear functions. The relationships between the parameters relate to the periodic functions and the shape of the generated attractors are analyzed. Theoretical investigations about the underlying mechanisms of the parallel striped attractors of fractional order system are presented, with the fractional order Lorenz, Rössler and Chua’s systems as examples. Moreover, the periodic doubling striped route to chaos of fractional order Rössler system and maximum Lyaponov exponent calculations are also given.     

Unitarily achievable zero patterns and traces of words in A and A

Our primary objective is to identify a natural and substantial problem about unitary similarity on arbitrary complex matrices: which 0-patterns may be achieved for any given n-by-n complex matrix via some unitary similarity of it. To this end, certain restrictions on “achievable” 0-patterns are mentioned, both positional and, more important, on the maximum number of achievable 0’s. Prior results fitting this general question are mentioned, as well as the “first” unresolved pattern (for 3-by-3 matrices!). In the process a recent question is answered.A closely related additional objective is to mention the best known bound for the maximum length of words necessary for the application of Specht’s theorem about which pairs of complex matrices are unitarily similar, which seems not widely known to matrix theorists. In the process, we mention the number of words necessary for small size matrices.     

The complexity of assigning genotypes to people in a pedigree consistently

We discuss the complexity of a combinatorial problem in the field of genetics, which we call Genotype ASsignability problem and abbreviate as GAS. A pair of genes at a position on a pair of chromosomes is called a genotype. GAS is defined as follows: “A pedigree is given and, for one of positions where genotypes are located in a set of pairs of chromosomes of a person, the genotypes at the position of some people in the pedigree are given. Is it possible to assign all other people (i.e., all of the people of which the genotypes are not given) genotypes for the position so as not to cause inconsistency in the heredity of genotypes at the position in the whole of the pedigree?” GAS can be used to compute, from the genotypes at the same position of some people in a pedigree, the genotypes that each person in the pedigree can possess at the position. Although many combinatorial problems have been studied so far, GAS seems not to have been done yet. Let m be the number of different genes in a pedigree and n that of people in the pedigree. We prove that GAS is NP-complete when m?3 and that it can be solved in linear time O(n) when m=2.