Hilbert Space of Probability Density Functions Based on Aitchison Geometry

The set of probability functions is a convex subset of L1 and it does not have a linear space structure when using ordinary sum and multiplication by real constants. Moreover, difficulties arise when dealing with distances between densities. The crucial point is that usual distances are not invariant under relevant transformations of densities. To overcome these limitations, Aitchison＇s ideas on compositional data analysis are used, generalizing perturbation and power transformation, as well as the Aitchison inner product, to operations on probability density functions with support on a finite interval. With these operations at hand, it is shown that the set of bounded probability density functions on finite intervals is a pre-Hilbert space. A Hilbert space of densities, whose logarithm is square-integrable, is obtained as the natural completion of the pre-Hilbert space.     

An improved max-flow-based lower bound for minimizing maximum lateness on identical parallel machines

In this paper, we introduce a new concept of semi-preemptive scheduling and we show how it can be used to derive a maximum-flow-based lower bound for the P|r_j|L_max which dominates the well-known preemptive lower bound. We show that, in some cases, the proposed bound strictly dominates the preemptive one while having the same complexity.     

A lower bound on the performance of the quadratic discriminant function

The quadratic discriminant function is often used to separate two classes of points in a multidimensional space. When the two classes are normally distributed, this results in the optimum separation. In some cases however, the assumption of normality is a poor one and the classification error is increased. The current paper derives an upper bound for the classification error due to a quadratic decision surface. The bound is strict when the class means and covariances and the quadratic discriminant surface satisfy certain specified symmetry conditions.     

A two-stage parallel branch and bound algorithm for mixed integer programs

Mixed integer programming (MIP) models are extensively usedto aid strategic and tactical decision making in many businesssectors. Solving MIP models is a computationally intensive processand there is a need to develop solution approaches that enablelarger models to be solved within acceptable timeframes. Inthis paper, we describe the implementation of a two-stage parallelbranch and bound (PB & B) algorithm for MIP. In stage 1of the algorithm, a multiple heuristic search is implementedin which a number of alternative search trees are investigatedusing a forest search in the hope of finding a good solutionquickly. In stage 2, the search is reorganized so that the branchesof a chosen tree are investigated in parallel. A new heuristicis introduced, based on a best projection criterion, which evaluatesalternative B & B trees in order to choose one for investigationin stage 2 of the algorithm. The heuristic also serves as away of implementing a quality load balancing scheme for stage2 of the algorithm. The results of experimental investigationsare reported for a range of models taken from the MIPLIB libraryof benchmark problems.     

A Note on Cactus Trees: Variational vs. Recursive Approach

In this article we deal with the variational approach to cactus trees (Husimi trees) and the more common recursive approach, that are in principle equivalent for finite systems. We discuss in detail the conditions under which the two methods are equivalent also in the analysis of infinite (self-similar) cactus trees, usually investigated to the purpose of approximating ordinary lattice systems. Such issue is hardly ever considered in the literature. We show (on significant test models) that the phase diagram and the thermodynamic quantities computed by the variational method, when they deviates from the exact bulk properties of the cactus system, generally provide a better approximation to the behavior of a corresponding ordinary system. Generalizing a property proved by Kikuchi, we also show that the numerical algorithm usually employed to perform the free energy minimization in the variational approach is always convergent.     

Randomization helps to perform independent tasks reliably

This paper is about algorithms that schedule tasks to be performed in a distributed failure‐prone environment, when processors communicate by message‐passing, and when tasks are independent and of unit length. The processors work under synchrony and may fail by crashing. Failure patterns are imposed by adversaries. Linearly‐bounded adversaries may fail up to a constant fraction of the processors. Weakly‐adaptive adversaries have to select, prior to the start of an execution, a subset of processors to be failure‐prone, and then may fail only the selected processors, at arbitrary steps, in the course of the execution. Strongly adaptive adversaries have a total number of failures as the only restriction on failure patterns. The measures of complexity are work, measured as the available processor steps, and communication, measured as the number of point‐to‐point messages. A randomized algorithm is developed, that attains both ??(n log*n) expected work and ??(n log*n) expected communication, against weakly‐adaptive linearly‐bounded adversaries, in the case when the numbers of tasks and processors are both equal to n. This is in contrast with performance of algorithms against strongly‐adaptive linearly‐bounded adversaries, which has to be Ω(n log n/log log n) in terms of work. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

On the advantage over a random assignment

We initiate the study of a new measure of approximation. This measure compares the performance of an approximation algorithm to the random assignment algorithm. This is a useful measure for optimization problems where the random assignment algorithm is known to give essentially the best possible polynomial time approximation. In this paper, we focus on this measure for the optimization problems Max‐Lin‐2 in which we need to maximize the number of satisfied linear equations in a system of linear equations modulo 2, and Max‐k‐Lin‐2, a special case of the above problem in which each equation has at most k variables. The main techniques we use, in our approximation algorithms and inapproximability results for this measure, are from Fourier analysis and derandomization. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Practical algorithms for transposition-invariant string-matching

We consider the problems of (1) longest common subsequence (LCS) of two given strings in the case where the first may be shifted by some constant (that is, transposed) to match the second, and (2) transposition-invariant text searching using indel distance. These problems have applications in music comparison and retrieval. We introduce two novel techniques to solve these problems efficiently. The first is based on the branch and bound method, the second on bit-parallelism. Our branch and bound algorithm computes the longest common transposition-invariant subsequence (LCTS) in time O((m²+loglogσ)logσ) in the best case and O((m²+logσ)σ) in the worst case, where m and σ, respectively, are the length of the strings and the size of the alphabet. On the other hand, we show that the same problem can be solved by using bit-parallelism and thus obtain a speedup of O(w/logm) over the classical algorithms, where the computer word has w bits. The advantage of this latter algorithm over the present bit-parallel ones is that it allows the use of more complex distances, including general integer weights. Since our branch and bound method is very flexible, it can be further improved by combining it with other efficient algorithms such as our novel bit-parallel algorithm. We experiment on several combination possibilities and discuss which are the best settings for each of those combinations. Our algorithms are easily extended to other musically relevant cases, such as δ-matching and polyphony (where there are several parallel texts to be considered). We also show how our bit-parallel algorithm is adapted to text searching and illustrate its effectiveness in complex cases where the only known competing method is the use of brute force.     

空间斜程能见度的影响因素分析

 空间斜程能见度是空间目标识别的重要参量。水平能见度与大气消光参数有明确的关系，而斜程能见度与大气消光参数、观测方向、太阳天顶角等多种因素有关，目前尚未有明确的结果。从辐射传输理论出发，通过δ-Eddington近似求解辐射传输方程，尝试推导了空间斜程能见度的表达式，探讨了斜程能见度与观察者视角、太阳高度角以及大气光学特性之间的关系。     

Spectral and Pseudospectral Approximations Using Hermite Functions: Application to the Dirac Equation

We consider in this paper spectral and pseudospectral approximations using Hermite functions for PDEs on the whole line. We first develop some basic approximation results associated with the projections and interpolations in the spaces spanned by Hermite functions. These results play important roles in the analysis of the related spectral and pseudospectral methods. We then consider, as an example of applications, spectral and pseudospectral approximations of the Dirac equation using Hermite functions. In particular, these schemes preserve the essential conservation property of the Dirac equation. We also present some numerical results which illustrate the effectiveness of these methods.