Kernel ideals and cokernel filters of a p-algebra

We discuss congruences of p-algebras. We characterize kernel ideals of a p-algebra. Indeed, we show that an ideal of a p-algebra is a p-ideal if and only if it is a kernel ideal. We study cokernel filters of a p-algebra. We construct a class of p-algebras in which every cokernel filter is a p-filter. We also give some characterizations of Boolean congruences of a p-algebra.     

Fractal methods and the problem of estimating scaling exponents: A new approach based on upper and lower linear bounds

The characterization of irregular objects with fractal methods often leads to the estimation of the slope of a function which is plotted versus a scale parameter. The slope is usually obtained with a linear regression. The problem is that the fit is usually not acceptable from the statistical standpoint. We propose a new approach in which we use two straight lines to bound the data from above and from below. We call these lines the upper and lower linear bounds. We propose to define these bounds as the solution of an optimization problem. We discuss the solution of this problem and we give an algorithm to obtain its solution. We use the difference between the upper and lower linear bounds to define a measure of the degree of linearity in the scaling range. We illustrate our method by analyzing the fluctuations of the variogram in a microresistivity well log from an oil reservoir in the North Sea.     

An optimal stocking problem to minimize the expected time to sellout

We consider an assortment planning problem where the objective is to minimize the expected time to sell all items in the assortment. We provide several structural results for the optimal assortment. We present a heuristic policy, which we prove is asymptotically optimal. We also show that there are alternate objective criteria under which the problem simplifies considerably.     

Spectral properties of three-electron systems in the Hubbard model

We investigate spectral properties of a three-electron system in the Hubbard model framework. We prove that the essential spectrum of the system in a quartet state consists of a single segment and the three-electron bound state is absent. We show that the essential spectrum of the system in doublet states is the union of at most three segments. We also prove that three-electron bound states exist in doublet states.     

The Complexity of Minimum Ratio Spanning Tree Problems

We examine the complexity of two minimum spanning tree problems with rational objective functions. We show that the Minimum Ratio Spanning Tree problem is NP-hard when the denominator is unrestricted in sign, thereby sharpening a previous complexity result. We then consider an extension of this problem where the objective function is the sum of two linear ratios whose numerators and denominators are strictly positive. This problem is shown to be NP-hard as well. We conclude with some results characterizing sufficient conditions for a globally optimal solution.     

Approximation by matrices with restricted spectra

We investigate the properties of the approximation of a matrix by matrices whose spectra are in a closed convex set of the complex plane. We explain why the Khalil and Maher characterization of an approximant, which spectrum is in a strip, is not quite correct. We prove that their characterization is valid but for another kind of approximation. We formulate a conjecture which leads to some algorithm for computing approximants. The conjecture is motivated by numerical experiments and some theoretical considerations. Separately we consider the approximation of normal matrices.     

The method of mechanical quadratures for integral equations with fixed singularity

We investigate the method of mechanical quadratures for integral equations with fixed singularity. We establish estimates of the error of this method based on a quadrature process, which is the best in the class of differentiable functions. We prove the convergence of the method in finite-dimensional and uniform metrics. We find that the investigated quadrature method is optimal by order on the Hölder class of functions.     

On Equilibria when Agents Have Multiple Priors

We discuss the existence and the qualitative properties of equilibria when agents have multiple priors and there is only one good in each state of the world. We first prove a general existence result in infinite dimension economies. We then fully describe the equilibria in two special cases. We first consider the case of CEU maximizers that have same capacities. We next consider the case of no aggregate uncertainty. We prove that if agents have non-random initial endowments and are uncertainty averse and maximize the minimal expected utility according to a set of possible priors, then the existence of a common prior is equivalent to the existence of a unique equilibrium, the no-trade equilibrium. We lastly give a mild assumption for indeterminacy of equilibria and compute the dimension of indeterminacy.     

Duality in nonlinear programming

In this paper are defined new first- and second-order duals of the nonlinear programming problem with inequality constraints. We introduce a notion of a WD-invex problem. We prove weak, strong, converse, strict converse duality, and other theorems under the hypothesis that the problem is WD-invex. We obtain that a problem with inequality constraints is WD-invex if and only if weak duality holds between the primal and dual problems. We introduce a notion of a second-order WD-invex problem with inequality constraints. The class of WD-invex problems is strictly included in the class of second-order ones. We derive that the first-order duality results are satisfied in the second-order case.     

Analysis of multi-stage open shop processing systems

We study algorithmic problems in multi-stage open shop processing systems that are centered around reachability and deadlock detection questions. We characterize safe and unsafe system states. We show that it is easy to recognize system states that can be reached from the initial state (where the system is empty), but that in general it is hard to decide whether one given system state is reachable from another given system state. We show that the problem of identifying reachable deadlock states is hard in general open shop systems, but is easy in the special case where no job needs processing on more than two machines (by linear programming and matching theory), and in the special case where all machines have capacity one (by graph-theoretic arguments).     

Consistent estimation of the intensity function of a cyclic Poisson process

We construct and investigate a consistent kernel-type nonparametric estimator of the intensity function of a cyclic Poisson process when the period is unknown. We do not assume any particular parametric form for the intensity function, nor do we even assume that it is continuous. Moreover, we consider the situation when only a single realization of the Poisson process is available, and only in a bounded window. We prove, in particular, that the proposed estimator is consistent when the size of the window indefinitely expands. We also obtain complete convergence of the estimator.     

Some problems of the theory of quantum statistical systems with an energy spectrum of the fractional-power type

We consider the problem of the effective interaction potential in a quantum many-particle system leading to the fractional-power dispersion law. We show that passing to fractional-order derivatives is equivalent to introducing a pair interparticle potential. We consider the case of a degenerate electron gas. Using the van der Waals equation, we study the equation of state for systems with a fractional-power spectrum. We obtain a relation between the van der Waals constant and the phenomenological parameter ??, the fractional-derivative order. We obtain a relation between energy, pressure, and volume for such systems: the coefficient of the thermal energy is a simple function of ??. We consider Bose??Einstein condensation in a system with a fractional-power spectrum. The critical condensation temperature for 1 < ?? < 2 is greater in the case under consideration than in the case of an ideal system, where ?? = 2.     

Authentication Codes in Plaintext and Chosen-Content Attacks

We study authentication codes (A-codes) when the enemy has access to the content of the intercepted cryptogram. This is similar to plaintext attack in secrecy systems. Enemy's success is defined in two ways. The first is as in Simmons' model. We will also consider chosen-content attacks in which the success is by constructing a fraudulent cryptogram with a given content. We will obtain information theoretic bounds, define perfect protection and obtain lower bounds on the number of encoding rules for codes with perfect protection against chosen-content impersonation and chosen-content plaintext substitution. We characterize these A-codes when the number of encoding rules is minimum. We give methods of making an A-code resistant against plaintext and chosen-context plaintext attack.Support for this project was aprtly provided by Australian Research Council.     

Partitions of Graphs into Cographs

Cographs from the minimal family of graphs containing K₁ which are closed with respect to complements and unions. We discuss vertex partitions of graphs into the smallest number of cographs, where the partition is as small as possible. We shall call the order of such a partition the c-chromatic number of the graph. We begin by axiomatizing several well-known graphical parameters as motivation for this function. We present several bounds on c-chromatic number in terms of well-known expressions. We show that if a graph is triangle-free, then its chromatic number is bounded between the c-chromatic number and twice this number. We show both bounds are sharp, for graphs with arbitrarily high girth. This provides an alternative proof to a result in [3]; there exist triangle-free graphs with arbitrarily large c-chromatic numbers. We show that any planar graph with girth at least 11 has a c-chromatic number of at most two. We close with several remarks on computational complexity. In particular, we show that computing the c-chromatic number is NP-complete for planar graphs.     

The one-warehouse multi-retailer problem: reformulation, classification, and computational results

We consider the one-warehouse multi-retailer problem where a warehouse replenishes multiple retailers with deterministic dynamic demands over a horizon. The problem is to determine when and how much to order to the warehouse and retailers such that the total system-wide costs are minimized. We propose a new (combined transportation and shortest path based) integer programming reformulation for the problem in addition to the echelon stock and transportation based formulations in the literature. We analyze the strength of the LP relaxations of three formulations and show that the new formulation is stronger than others. We also show that the new and transportation based formulations are equivalent for the joint replenishment problem, where the warehouse is a crossdocking facility. We extend all formulations to the case with initial inventory at the warehouse and reveal the relation among their LP relaxations. We present our computational experiments with all formulations over a set of randomly generated test instances.     

An analysis of a widely used version of the CUSUM tracking signal

Tracking signals are used to determine whether a sequence of forecasts is unbiased. We analyse a version of the CUSUM tracking signal that is based on the unsmoothed average mean absolute deviation of forecasting errors. We make the common assumption that demand values in different periods are independently, identically, and normally distributed. We show that, when forecast errors in different periods are also normal iid, this version of the tracking signal can indicate that the sequence is not unbiased even when it is unbiased. We suggest a simple modification to the tracking signal that serves to eliminate this flaw.     

A Signature Scheme Based on the Intractability of Computing Roots

We present RDSA, a variant of the DSA signature scheme, whose security is based on the intractability of extracting roots in a finite abelian group. We prove that RDSA is secure against an adaptively chosen message attack in the random oracle model if and only if computing roots in the underlying group is intractable. We report on a very efficient implementation of RDSA in the class group of imaginary quadratic orders. We also show how to construct class groups of algebraic number fields of degree < 2 in which RDSA can be implemented.     

When does the Haver property imply selective screenability?

We point out that in metric spaces Haver's property is not equivalent to the property introduced by Addis and Gresham. We prove that they are equal when the space has the Hurewicz property. We prove several results about the preservation of Haver's property in products. We show that if a separable metric space has the Haver property, and the nth power has the Hurewicz property, then the nth power has the Addis-Gresham property. R. Pol showed earlier that this is not the case when the Hurewicz property is replaced by the weaker Menger property. We introduce new classes of weakly infinite dimensional spaces.     

Generalizing variance to allow the inclusion of decision attitude in decision making under uncertainty

The problem of decision making under uncertainty is considered. It is noted that an alternative is described in terms of an uncertainty profile. We observe that a major difficulty in the decision process is the comparison of these uncertainty profiles. We discuss the need for introducing some features of an uncertainty profile to help simplify this comparison. We note that the quantification of these simplifying features involves some subjective considerations about the decision makers preferences. We introduce the idea of the decision maker’s attitudinal character to help in the formulation of these considerations. We then investigate two important features associated with an uncertainty profile. The first, the representative value, is a generalization of expected value commonly used under probabilistic uncertainty. The second, called the measure of deviation, provides a generalization of the concept of variance. We show how these new measures allows us to consider uncertainty profiles other then just the probabilistic one. They also allow us introduce other decision maker attitudes then the one implicitly assumed with the expected value and variance.