Metal location and thickness in a multilayered sheet by measuring K alpha/K beta, L alpha/L beta and L alpha/L gamma X-ray ratios

When a multilayered material is analyzed by means of energy-dispersive X-ray fluorescence analysis, then the X-ray ratios of K alpha/K beta, or L alpha/L beta and L alpha/L gamma, for an element in the multilayered material, depend on the composition and thickness of the layer in which the element is situated, and on the composition and thickness of the superimposed layer (or layers). Multilayered samples are common in archaeometry, for example, in the case of pigment layers in paintings, or in the case of gilded or silvered alloys. The latter situation is examined in detail in the present paper, with a specific reference to pre-Columbian alloys from various museums in the north of Peru. (C) 2009 Elsevier B.V. All rights reserved.

A novel MAP-MRF approach for multispectral image contextual classification using combination of suboptimal iterative algorithms

In this paper we present a novel approach for multispectral image contextual classification by combining iterative combinatorial optimization algorithms. The pixel-wise decision rule is defined using a Bayesian approach to combine two MRF models: a Gaussian Markov Random Field (GMRF) for the observations (likelihood) and a Potts model for the a priori knowledge, to regularize the solution in the presence of noisy data. Hence, the classification problem is stated according to a Maximum a Posteriori (MAP) framework. In order to approximate the MAP solution we apply several combinatorial optimization methods using multiple simultaneous initializations, making the solution less sensitive to the initial conditions and reducing both computational cost and time in comparison to Simulated Annealing, often unfeasible in many real image processing applications. Markov Random Field model parameters are estimated by Maximum Pseudo-Likelihood (MPL) approach, avoiding manual adjustments in the choice of the regularization parameters. Asymptotic evaluations assess the accuracy of the proposed parameter estimation procedure. To test and evaluate the proposed classification method, we adopt metrics for quantitative performance assessment (Cohen`s Kappa coefficient), allowing a robust and accurate statistical analysis. The obtained results clearly show that combining sub-optimal contextual algorithms significantly improves the classification performance, indicating the effectiveness of the proposed methodology. (C) 2010 Elsevier B.V. All rights reserved.

PARALLEL ALGORITHMS FOR MAXIMAL CLIQUES IN CIRCLE GRAPHS AND UNRESTRICTED DEPTH SEARCH

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O(log p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.

Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K(2)}. In this paper we provide new approximation algorithms and hardness results for the K(r)-packing problem where K(r) = {K(2), K(3,) . . . , K(r)}. We show that already for r = 3 the K(r)-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation. (C) 2008 Elsevier B.V. All rights reserved.

Algorithms for Maximum Independent Set in Convex Bipartite Graphs

A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v. V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|.

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Preferential location of lidocaine and etidocaine in lecithin bilayers as determined by EPR, fluorescence and H-2 NMR

We have examined the effect of the uncharged species of lidocaine (LDC) and etidocaine (EDC) on the acyl chain moiety of egg phosphatidylcholine liposomes. Changes in membrane organization caused by both anesthetics were detected through the use of EPR spin labels (5, 7 and 12 doxyl stearic acid methyl ester) or fluorescence probes (4, 6, 10, 16 pyrene-fatty acids). The disturbance caused by the LA was greater when the probes were inserted in more external positions of the acyl chain and decreased towards the hydrophobic core of the membrane. The results indicate a preferential insertion of LDC at the polar interface of the bilayer and in the first half of the acyl chain, for EDC. Additionally, 2 H NMR spectra of multilamellar liposomes composed by acyl chain-perdeutero DMPC and EPC (1:4 mol%) allowed the determination of the segmental order (S-mol) and dynamics (T-1) of the acyl chain region. In accordance to the fluorescence and EPR results, changes in molecular orientation and dynamics are more prominent if the LA preferential location is more superficial, as for LDC while EDC seems to organize the acyl chain region between carbons 2-8, which is indicative of its positioning. We propose that the preferential location of LDC and EDC inside the bilayers creates a ""transient site"", which is related to the anesthetic potency since it could modulate the access of these molecules to their binding site(s) in the voltage-gated sodium channel. (C) 2007 Elsevier B.V. All rights reserved.