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.     

On perturbations of matrix pencils with real spectra, a revisit

This paper continues earlier studies by Bhatia and Li on eigenvalue perturbation theory for diagonalizable matrix pencils having real spectra. A unifying framework for creating crucial perturbation equations is developed. With the help of a recent result on generalized commutators involving unitary matrices, new and much sharper bounds are obtained.

     

Regularity of Harmonic Functions in Cheeger-Type Sobolev Spaces

We give a geometric approach to the study of the regularity of harmonic functions in Cheeger-type Sobolev spaces, and prove the Hölder continuity of such functions. In the proof, we give a definition of an upper curvature bound of the unit sphere of a Banach space, which seems to be of independent interest.     

Global error bound for convex inclusion problems

The existence of global error bound for convex inclusion problems is discussed in this paper, including pointwise global error bound and uniform global error bound. The existence of uniform global error bound has been carefully studied in Burke and Tseng (SIAM J. Optim. 6(2), 265–282, 1996) which unifies and extends many existing results. Our results on the uniform global error bound (see Theorem 3.2) generalize Theorem 9 in Burke and Tseng (1996) by weakening the constraint qualification and by widening the varying range of the parameter. As an application, the existence of global error bound for convex multifunctions is also discussed.     

串联系统可靠性虚拟系统法置信下限的小样本性质

本文讨论了具有r个成败型元件串联系统可靠性的置信下限问题。研究了虚拟系统法置信下限的小样本性质,证明了,在通常情况下虚拟系统法置信下限要大于常见的L-M法置信下限.更一般地,本文证明了在成败型试验中,当成功数与试验数之比保持不变时,试验次数的增加将直接缩小成功率置信区间的长度。     

一类几乎最优循环图{C_p(m,m+1,p/a)}

本文比较了循环图类{c_p(n_1,…,n_p)}和{c-p(n_1…,n_p,p/α)}的直径下界。对于p和α满足一定条件的循环图类{c_p(n_1,n_2,p/α)},本文给出了达到或几乎达到此图类直径下界的一类几乎最优循环图{c_p(m,m+1,p/α)}。     

等式与界约束非线性优化信赖域算法的全局收敛

§ 1　ＩｎｔｒｏｄｕｃｔｉｏｎＣｏｎｓｉｄｅｒｔｈｅｆｏｌｌｏｗｉｎｇｎｏｎｌｉｎｅａｒｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍ :ｍｉｎｉｍｉｚｅｆ(ｘ)ｓｕｂｊｅｃｔｔｏＣ(ｘ) =0 ,　ａ≤ｘ≤ｂ ,( 1 .1 )ｗｈｅｒｅｆ(ｘ) :Ｒｎ→Ｒ ,Ｃ(ｘ) =(ｃ1(ｘ) ,ｃ2 (ｘ) ,...,ｃｍ(ｘ) ) Ｔ:Ｒｎ→Ｒｍ ａｒｅｔｗｉｃｅｃｏｎｔｉｎｕｏｕｓｌｙｄｉｆｆｅｒｅｎｔｉａｂｌｅ,ｍ≤ｎ ,ａ ,ｂ∈Ｒｎ.Ｔｒｕｓｔｒｅｇｉｏｎａｌｇｏｒｉｔｈｍｓａｒｅｖｅｒｙｅｆｆｅｃｔｉｖｅｆｏｒｓｏｌｖｉｎｇｎｏｎｌｉｎｅａｒｏｐｔｉｍｉ…     

Continuity of the Solution Map in Parametric Affine Variational Inequalities

A systematic study of the upper semicontinuity and the lower semicontinuity of the solution map in parametric affine variational inequalities is given in this paper. Several examples are constructed to analyze the results. This work was supported by Korea Research Foundation Grant (KRF 2001-015-DP0049), the APEC Postdoctoral Fellowships Program, and the KOSEF Brain Pool Program.     

The solution existence of general variational inclusion problems

We propose general variational inclusion problems which are slightly different from corresponding problems considered in several recent papers in the literature and show that they are advantageous. Sufficient conditions for the solution existence are established. As applications we derive consequences for several special cases of variational inclusion problems, quasioptimization problems, equilibrium problems and implicit variational inequalities and show that they improve the results of some recent existing papers.     

Idempotency of Extensions via the Bicompletion

Let Top ₀ be the category of topological T ₀-spaces, QU ₀ the category of quasi-uniform T ₀-spaces, T : QU ₀ → Top ₀ the usual forgetful functor and K : QU ₀ → QU ₀ the bicompletion reflector with unit k : 1 → K. Any T-section F : Top ₀ → QU ₀ is called K-true if KF = FTKF, and upper (lower) K-true if KF is finer (coarser) than FTKF. The literature considers important T-sections F that enjoy all three, or just one, or none of these properties. It is known that T(K,k)F is well-pointed if and only if F is upper K-true. We prove the surprising fact that T(K,k)F is the reflection to Fix(TkF) whenever it is idempotent. We also prove a new characterization of upper K-trueness. We construct examples to set apart some natural cases. In particular we present an upper K-true F for which T(K,k)F is not idempotent, and a K-true F for which the coarsest associated T-preserving coreflector in QU ₀ is not stable under K. We dedicate this paper to the memory of Sérgio de Ornelas Salbany (1941–2005).