Approximating a class of combinatorial problems with rational objective function

In the late seventies, Megiddo proposed a way to use an algorithm for the problem of minimizing a linear function a(0) + a(1)x(1) + ... + a(n)x(n) subject to certain constraints to solve the problem of minimizing a rational function of the form (a(0) + a(1)x(1) + ... + a(n)x(n))/(b(0) + b(1)x(1) + ... + b(n)x(n)) subject to the same set of constraints, assuming that the denominator is always positive. Using a rather strong assumption, Hashizume et al. extended Megiddo`s result to include approximation algorithms. Their assumption essentially asks for the existence of good approximation algorithms for optimization problems with possibly negative coefficients in the (linear) objective function, which is rather unusual for most combinatorial problems. In this paper, we present an alternative extension of Megiddo`s result for approximations that avoids this issue and applies to a large class of optimization problems. Specifically, we show that, if there is an alpha-approximation for the problem of minimizing a nonnegative linear function subject to constraints satisfying a certain increasing property then there is an alpha-approximation (1 1/alpha-approximation) for the problem of minimizing (maximizing) a nonnegative rational function subject to the same constraints. Our framework applies to covering problems and network design problems, among others.

Forest structure in a mosaic of rainforest sites: The effect of fragmentation and recovery after clear cut

A variety of human-induced disturbances such as forest fragmentation and recovery after deforestation for pasture or agricultural activities have resulted in a complex landscape mosaic in the Una region of northeastern Brazil. Using a set of vegetation descriptors, we investigated the main structural changes observed in forest categories that comprise the major components of the regional landscape and searched for potential key descriptors that could be used to discriminate among different forest categories. We assessed the forest structure of five habitat categories defined as (I) interiors and (2) edges of large fragments of old-growth forest (>1000 ha), (3) interiors and (4) edges of small forest fragments (<100 ha), and (5) early secondary forests. Forest descriptors used here were: frequency of herbaceous lianas and woody climbers, number of standing dead trees, number of fallen trunks, litter depth, number of pioneer plants (early secondary and shade-intolerant species), vertical foliage stratification profile and distribution Of trees in different diameter classes. Edges and interiors of forest fragments were significantly different only in the number of standing dead trees. Secondary forests and edges of fragments showed differences in litter depth, fallen trunks and number of pioneer trees, and secondary forests were significantly different from fragment interiors in the number of standing dead trees and the number of pioneer trees. Horizontal and vertical structure evaluated via ordination analysis showed that fragment interiors, compared to secondary forests, were characterized by a greater number of medium (25-35 cm) and large (35-50 cm) trees and smaller numbers of thin trees (5-10 cm). There was great heterogeneity at the edges of small and large fragments, as these sites were distributed along almost the entire gradient. Most interiors of large and small fragments presented higher values of foliage densities at higher strata ( 15-20 m and at 20-25 m height), and lower densities at 1-5 m. All secondary forests and some fragment edge sites showed an opposite tendency. A discriminant function highlighted differences among forest categories, with transects of large fragment interiors and secondary forests representing two extremes along a disturbance gradient determined by foliage structure (densities at 15-20 m and 20-25 m), with the edges of both large and small fragments and the interiors of small fragments scattered across the gradient. The major underlying processes determining patterns of forest disturbance in the study region are discussed, highlighting the importance of forest fragments, independently of its size, as forests recovery after clear cut show a greatly distinct structure, with profound implications on fauna movements. (C) 2009 Elsevier BY. All rights reserved.

New species of the bee genus Augochlorodes Moure (Hymenoptera, Apidae s. I., Halictinae)

Five new species of the bee genus Augochlorodes from Brazil are described and the type species, A. turrifaciens Moure, 1958, is redescribed. The new species are: A. clementis sp. nov. (from the states of Parana, Santa Catarina and Rio Grande do Sul), A. incomitatus sp. nov. (Rio Grande do Sul), A. politus sp. nov. (Parana), A. rostratus sp. nov. (Rio Grande do Sul) and A. vachali sp. nov. (Parana, Santa Catarina, Sao Paulo). A discriminant function analysis using head measurements is presented to help distinguish the species. An identification key for the species is provided.

ENHANCING MULTISCALE FRACTAL DESCRIPTORS USING FUNCTIONAL DATA ANALYSIS

This work presents a novel approach in order to increase the recognition power of Multiscale Fractal Dimension (MFD) techniques, when applied to image classification. The proposal uses Functional Data Analysis (FDA) with the aim of enhancing the MFD technique precision achieving a more representative descriptors vector, capable of recognizing and characterizing more precisely objects in an image. FDA is applied to signatures extracted by using the Bouligand-Minkowsky MFD technique in the generation of a descriptors vector from them. For the evaluation of the obtained improvement, an experiment using two datasets of objects was carried out. A dataset was used of characters shapes (26 characters of the Latin alphabet) carrying different levels of controlled noise and a dataset of fish images contours. A comparison with the use of the well-known methods of Fourier and wavelets descriptors was performed with the aim of verifying the performance of FDA method. The descriptor vectors were submitted to Linear Discriminant Analysis (LDA) classification method and we compared the correctness rate in the classification process among the descriptors methods. The results demonstrate that FDA overcomes the literature methods (Fourier and wavelets) in the processing of information extracted from the MFD signature. In this way, the proposed method can be considered as an interesting choice for pattern recognition and image classification using fractal analysis.

Comparison for three Classification Techniques

In this paper we show the results of a comparison simulation study for three classification techniques: Multinomial Logistic Regression (MLR), No Metric Discriminant Analysis (NDA) and Linear Discriminant Analysis (LDA). The measure used to compare the performance of the three techniques was the Error Classification Rate (ECR). We found that MLR and LDA techniques have similar performance and that they are better than DNA when the population multivariate distribution is Normal or Logit-Normal. For the case of log-normal and Sinh(-1)-normal multivariate distributions we found that MLR had the better performance.

Comparing performance of instrumental drift correction by linear and quadratic adjusting in inductive electromagnetic data

Electromagnetic induction (EMI) method results are shown for vertical magnetic dipole (VMD) configuration by using the EM38 equipment. Performance in the location of metallic pipes and electrical cables is compared as a function of instrumental drift correction by linear and quadratic adjusting under controlled conditions. Metallic pipes and electrical cables are buried at the IAG/USP shallow geophysical test site in Sao Paulo City. Brazil. Results show that apparent electrical conductivity and magnetic susceptibility data were affected by ambient temperature variation. In order to obtain better contrast between background and metallic targets it was necessary to correct the drift. This correction was accomplished by using linear and quadratic relation between conductivity/susceptibility and temperature intending comparative studies. The correction of temperature drift by using a quadratic relation was effective, showing that all metallic targets were located as well deeper targets were also improved. (C) 2010 Elsevier B.V. All rights reserved.

Exact Search Directions for Optimization of Linear and Nonlinear Models Based on Generalized Orthonormal Functions

A novel technique for selecting the poles of orthonormal basis functions (OBF) in Volterra models of any order is presented. It is well-known that the usual large number of parameters required to describe the Volterra kernels can be significantly reduced by representing each kernel using an appropriate basis of orthonormal functions. Such a representation results in the so-called OBF Volterra model, which has a Wiener structure consisting of a linear dynamic generated by the orthonormal basis followed by a nonlinear static mapping given by the Volterra polynomial series. Aiming at optimizing the poles that fully parameterize the orthonormal bases, the exact gradients of the outputs of the orthonormal filters with respect to their poles are computed analytically by using a back-propagation-through-time technique. The expressions relative to the Kautz basis and to generalized orthonormal bases of functions (GOBF) are addressed; the ones related to the Laguerre basis follow straightforwardly as a particular case. The main innovation here is that the dynamic nature of the OBF filters is fully considered in the gradient computations. These gradients provide exact search directions for optimizing the poles of a given orthonormal basis. Such search directions can, in turn, be used as part of an optimization procedure to locate the minimum of a cost-function that takes into account the error of estimation of the system output. The Levenberg-Marquardt algorithm is adopted here as the optimization procedure. Unlike previous related work, the proposed approach relies solely on input-output data measured from the system to be modeled, i.e., no information about the Volterra kernels is required. Examples are presented to illustrate the application of this approach to the modeling of dynamic systems, including a real magnetic levitation system with nonlinear oscillatory behavior.

Fock space for fermion-like lattices and the linear Glauber model

The concept of Fock space representation is developed to deal with stochastic spin lattices written in terms of fermion operators. A density operator is introduced in order to follow in parallel the developments of the case of bosons in the literature. Some general conceptual quantities for spin lattices are then derived, including the notion of generating function and path integral via Grassmann variables. The formalism is used to derive the Liouvillian of the d-dimensional Linear Glauber dynamics in the Fock-space representation. Then the time evolution equations for the magnetization and the two-point correlation function are derived in terms of the number operator. (C) 2008 Elsevier B.V. All rights reserved.

Magnetic linear dichroism in absorption spectroscopy of EuTe

The magnetic linear dichroism (MLD) at band-edge photon energies in the Voigt geometry was calculated for EuTe. At the spin-flop transition, MLD shows a step-like increase. Above the spin-flop transition MLD slowly decreases and becomes zero when the averaged electronic charge becomes symmetric relative to the axis of light propagation. Further increase of the magnetic field causes ferromagnetic alignment of the spins along the magnetic field direction, and MLD is recovered but with an opposite sign, and reaches maximum absolute values. These results are explained by the rearrangement of the Eu(2+) spin distribution in the crystal lattice as a function of magnetic field, due to the Zeeman interaction, demonstrating that MLD can be a sensitive probe of the spin order in EuTe, and provides information that is not accessible from other magneto-optical techniques, such as magnetic circular dichroism measurement studies.

Improved testing inference in mixed linear models

Mixed linear models are commonly used in repeated measures studies. They account for the dependence amongst observations obtained from the same experimental unit. Often, the number of observations is small, and it is thus important to use inference strategies that incorporate small sample corrections. In this paper, we develop modified versions of the likelihood ratio test for fixed effects inference in mixed linear models. In particular, we derive a Bartlett correction to such a test, and also to a test obtained from a modified profile likelihood function. Our results generalize those in [Zucker, D.M., Lieberman, O., Manor, O., 2000. Improved small sample inference in the mixed linear model: Bartlett correction and adjusted likelihood. Journal of the Royal Statistical Society B, 62,827-838] by allowing the parameter of interest to be vector-valued. Additionally, our Bartlett corrections allow for random effects nonlinear covariance matrix structure. We report simulation results which show that the proposed tests display superior finite sample behavior relative to the standard likelihood ratio test. An application is also presented and discussed. (C) 2008 Elsevier B.V. All rights reserved.

Local Influence Analysis for Skew-Normal Linear Mixed Models

In this article, we consider local influence analysis for the skew-normal linear mixed model (SN-LMM). As the observed data log-likelihood associated with the SN-LMM is intractable, Cook`s well-known approach cannot be applied to obtain measures of local influence. Instead, we develop local influence measures following the approach of Zhu and Lee (2001). This approach is based on the use of an EM-type algorithm and is measurement invariant under reparametrizations. Four specific perturbation schemes are discussed. Results obtained for a simulated data set and a real data set are reported, illustrating the usefulness of the proposed methodology.

Chemical profile of rums as a function of their origin. The use of chemometric techniques for their identification

To identify chemical descriptors to distinguish Cuban from non-Cuban rums, analyses of 44 samples of rum from 15 different countries are described. To provide the chemical descriptors, analyses of the the mineral fraction, phenolic compounds, caramel, alcohols, acetic acid, ethyl acetate, ketones, and aldehydes were carried out. The analytical data were treated through the following chemometric methods: principal component analysis (PCA), partial least square-discriminate analysis (PLS-DA), and linear discriminate analysis (LDA). These analyses indicated 23 analytes as relevant chemical descriptors for the separation of rums into two distinct groups. The possibility of clustering the rum samples investigated through PCA analysis led to an accumulative percentage of 70.4% in the first three principal components, and isoamyl alcohol, n-propyl alcohol, copper, iron, 2-furfuraldehyde (furfuraldehyde), phenylmethanal (benzaldehyde), epicatechin, and vanillin were used as chemical descriptors. By applying the PLS-DA technique to the whole set of analytical data, the following analytes have been selected as descriptors: acetone, sec-butyl alcohol, isobutyl alcohol, ethyl acetate, methanol, isoamyl alcohol, magnesium, sodium, lead, iron, manganese, copper, zinc, 4-hydroxy3,5-dimethoxybenzaldehyde (syringaldehyde), methaldehyde (formaldehyde), 5-hydroxymethyl-2furfuraldehyde (5-HMF), acetalclehyde, 2-furfuraldehyde, 2-butenal (crotonaldehyde), n-pentanal (valeraldehyde), iso-pentanal (isovaleraldehyde), benzaldehyde, 2,3-butanodione monoxime, acetylacetone, epicatechin, and vanillin. By applying the LIDA technique, a model was developed, and the following analytes were selected as descriptors: ethyl acetate, sec-butyl alcohol, n-propyl alcohol, n-butyl alcohol, isoamyl alcohol, isobutyl alcohol, caramel, catechin, vanillin, epicatechin, manganese, acetalclehyde, 4-hydroxy-3-methoxybenzoic acid, 2-butenal, 4-hydroxy-3,5-dimethoxybenzoic acid, cyclopentanone, acetone, lead, zinc, calcium, barium, strontium, and sodium. This model allowed the discrimination of Cuban rums from the others with 88.2% accuracy.