Informatica

We address the issue of inapproximability of the wavelength assignment problem in wavelength division multiplexing (WDM) optical networks. We prove that in an n-node WDM optical network with m lightpaths and maximum load L, if NP ≠ ZPP, for any constant δ>0, no polynomial time algorithm can achieve approximation ratio n^1/2−δ or m^1−δ, where NP is the class of problems which can be solved by nondeterministic polynomial time algorithms, and ZPP is the class of problems that can be solved by polynomial randomized algorithms with zero probability of error. Furthermore, the above result still holds even when L=2. We also prove that no algorithm can guarantee the number of wavelengths to be less than $(\sqrt{n}/2)L$ or (m/2)L. This is the first time inapproximability results are established for the wavelength assignment problem in WDM optical networks. We also notice the following fact, namely, there is a polynomial time algorithm for wavelength assignment which achieves approximation ratio of O(m(log log m)²/(log m)³). Therefore, the above lower bound of m^1−δ is nearly tight.

Transient evoked otoacoustic emissions (TEOAEs) have been analyzed for objective assessment of hearing function and monitoring of the influence of noise exposure and ototoxic drugs. This paper presents a novel application of the Hilbert–Huang transform (HHT) for detection and time-frequency mapping of TEOAEs. Since the HHT does not distinguish between signal and noise, it is combined with ensemble correlation in order to extract signal information in intervals with correlated activity. High resolution time-frequency mapping could predict 30 dBHL, or higher hearing loss, at different audiological frequencies in 63–90% of the cases and normal hearing in 75–90% of the cases. The proposed method offers TEOAE time-frequency mapping by constraining the analysis to regions with high signal-to-noise ratios. The results suggest that the HHT is suitable for hearing loss detection at individual frequencies and characterization of the fine structures of TEOAEs.

This paper presents an improved differential evolution (IDE) method for the solution of large-scale unit commitment (UC) problems. The objective of the proposed scheme is to determine the generation schedule which minimizes the total operating cost over a given time horizon subject to a variety of constraints. Through its use of enhanced acceleration and migration processes, the IDE method limits the population size required in the search procedure and is therefore an ideal candidate for the solution of large-scale combinatorial optimization problems. The effectiveness of the proposed approach is verified by performing a series of simulations based upon the practical Tai-Power System (TPS) and various other power systems presented in the literature. In general, the results show that the IDE scheme outperforms existing deterministic and stochastic optimization methods both in terms of the quality of the solutions obtained and the computational cost. Furthermore, it is found that the magnitude of the cost savings achieved by the IDE scheme compared to that obtained by the other optimization techniques increases as the number of generating units within the power system increases. Therefore, the proposed scheme represents a particularly effective technique for the solution of large-scale UC problems.

Least-squares method is the most popular method for parameter estimation. It is easy applicable, but it has considerable drawback. Under well-known conditions in the presence of noise, the LS method produces asymptotically biased and inconsistent estimates. One way to overcome this drawback is the implementation of the instrumental variable method. In this paper several modifications of this method for closed-loop system identification are considered and investigated. The covariance matrix of the instrumental variable estimates is discussed. A simulation is carried out in order to illustrate the obtained results.

The optimization problems occurring in nonlinear regression normally cannot be proven unimodal. In the present paper applicability of global optimization algorithms to this problem is investigated with the focus on interval arithmetic based algorithms.

The paper deals with the recursive identification of dynamic systems having noninvertible output characteristics, which can be represented by the Wiener model. A special form of the model is considered where the linear dynamic block is given by its transfer function and the nonlinear static block is characterized by such a description of the piecewise-linear characteristic, which is appropriate for noninvertible nonlinearities. The proposed algorithm is a direct application of the known recursive least squares method extended with the estimation of internal variables and enables the on-line estimation of both the linear block parameters and the parameters of some noninvertible nonlinearities and their changes. The feasibility of the proposed method is illustrated on examples of time-varying systems.

In stochastic programming and decision analysis, an important issue consists in the approximate representation of the multidimensional stochastic underlying process in the form of scenario tree. This paper presents the approach to generate the multistage multidimensional scenario tree out of a set of scenario fans. For this purpose, the multistage K-means clustering algorithm is developed. The presented scenario tree generation algorithm is motivated by the stability results for optimal values of a multistage stochastic program. The time complexity of developed multistage K-means clustering algorithm is proved to be linear in regard to the number of scenarios in the fan. The algorithm to determine the branches with nonduplicate information in the multistage scenario tree is also presented as an intermediate result of research.

In 2007, Kancharla et al. proposed an identity-based strong designated verifier signature (IBSDVS) scheme based on bilinear pairings, and claimed it unforgeable and non-delegatable. However, in this paper, we show that this scheme is actually delegatable.

We address the problem of statistical machine translation from highly inflective language to less inflective one. The characteristics of inflective languages are generally not taken into account by the statistical machine translation system. Existing translation systems often treat different inflected word forms of the same lemma as if they were independent of each other, although some interdependencies exist. On the other hand we know that if we reduce inflected word forms to common lemmas, some information is lost. It would be reasonable to eliminate only the variations in inflected word forms, which are not relevant for translation. Inflectional features of words are defined by morpho-syntactic descriptions (MSD) tags and we want reduce them. To do this the explicit knowledge about both languages (source and target language) is needed. The idea of the paper is to find the information-bearing MSDs in source language by data-driven approach. The task is performed by a global optimization algorithm, named Differential Evolution. The experiments were performed using freely available parallel English–Slovenian corpus SVEZ-IJS, which is lemmatized and annotated with MSD tags. The results show a promising direction toward optimal subset of morpho-syntactic features.

In the previous papers (Pupeikis, 2000; Genov et al., 2006; Atanasov and Pupeikis, 2009), a direct approach for estimating the parameters of a discrete-time linear time-invariant (LTI) dynamic system, acting in a closed-loop in the case of additive noise with contaminating outliers uniformly spread in it, is presented. It is assumed there that the parameters of the LQG (Linear Quadratic Gaussian) controller are unknown, as well as known beforehand, too. The aim of the given paper is development of a minimum variance control (MVC) approach for a closed-loop discrete-time linear dynamic system when slowly or suddenly time-varying coefficients of the transfer function of such a system as well as that of a minimum variance (MV) controller are not known and ought to be estimated. The recursive parametric identification of an open-loop system and determination of the coefficients of the MV controller are performed in each current operation by processing observations in the case of additive noise at the output with contaminating outliers uniformly spread in it. The robust recursive technique, based on the S-algorithm, with a version of Shweppe's GM-estimator and with discounting previous data, used in the estimation, by introducing a constant as well as time-varying forgetting factors in the abovementioned estimator, is applied here in the calculation of estimates of the parameters of a dynamic system. Then, the recursive parameter estimates are used in each current iteration to determine unknown parameters of the MV controller. Afterwards, the current value of the MV control signal is found in each operation, and it is used to generate the output of the system, too. The results of numerical simulation by computer are presented and discussed.