The Linear Ordering Problem Revisited

The Linear Ordering Problem is a popular combinatorial optimisation problem which has been extensively addressed in the literature. However, in spite of its popularity, little is known about the characteristics of this problem. This paper studies a procedure to extract static information from an instance of the problem, and proposes a method to incorporate the obtained knowledge in order to improve the performance of local search-based algorithms. The procedure introduced identifies the positions where the indexes cannot generate local optima for the insert neighbourhood, and thus global optima solutions. This information is then used to propose a restricted insert neighbourhood that discards the insert operations which move indexes to positions where optimal solutions are not generated. In order to measure the efficiency of the proposed restricted insert neighbourhood system, two state-of-the-art algorithms for the LOP that include local search procedures have been modified. Conducted experiments confirm that the restricted versions of the algorithms outperform the classical designs systematically. The statistical test included in the experimentation reports significant differences in all the cases, which validates the efficiency of our proposal.

Downscaling of surface moisture flux and precipitation in the Ebro Valley (Spain) using analogues and analogues followed by random forests and multiple linear regression

In this paper, reanalysis fields from the ECMWF have been statistically downscaled to predict from large-scale atmospheric fields, surface moisture flux and daily precipitation at two observatories (Zaragoza and Tortosa, Ebro Valley, Spain) during the 1961-2001 period. Three types of downscaling models have been built: (i) analogues, (ii) analogues followed by random forests and (iii) analogues followed by multiple linear regression. The inputs consist of data (predictor fields) taken from the ERA-40 reanalysis. The predicted fields are precipitation and surface moisture flux as measured at the two observatories. With the aim to reduce the dimensionality of the problem, the ERA-40 fields have been decomposed using empirical orthogonal functions. Available daily data has been divided into two parts: a training period used to find a group of about 300 analogues to build the downscaling model (1961-1996) and a test period (19972001), where models' performance has been assessed using independent data. In the case of surface moisture flux, the models based on analogues followed by random forests do not clearly outperform those built on analogues plus multiple linear regression, while simple averages calculated from the nearest analogues found in the training period, yielded only slightly worse results. In the case of precipitation, the three types of model performed equally. These results suggest that most of the models' downscaling capabilities can be attributed to the analogues-calculation stage.

Deformation Of Pdms Membrane And Microcantilever By A Water Droplet: Comparison Between Mooney-Rivlin And Linear Elastic Constitutive Models

In this paper, we studied the role of vertical component Of Surface tension of a water droplet on the deformation of membranes and microcantilevers (MCLs) widely used in lab-on-a-chip and micro-and nano-electromechanical system (MEMS/NEMS). Firstly, a membrane made of a rubber-like material, poly(dimethylsiloxane) (PDMS), was considered. The deformation was investigated using the Mooney-Rivlin (MR) model and the linear elastic constitutive relation, respectively. By comparison between the numerical solutions with two different models, we found that the simple linear elastic model is accurate enough to describe such kind of problem, which would be quite convenient for engineering applications. Furthermore, based on small-deflection beam theory, the effect of a liquid droplet on the deflection of a MCL was also studied. The free-end deflection of the MCL was investigated by considering different cases like a cylindrical droplet, a spherical droplet centered on the MCL and a spherical droplet arbitrarily positioned on the MCL. Numerical simulations demonstrated that the deflection might not be neglected, and showed good agreement with our theoretical analyses. (C) 2008 Elsevier Inc. All rights reserved.

Design, analysis and implementation of a versatile low level radio frequency system for accelerating cavities

179 p.

The Convective Instabilities in a Liquid-Vapor System with a Non-equilibrium Evaporation Interface

Rayleigh-Marangoni-B,nard instability in a system consisting of a horizontal liquid layer and its own vapor has been investigated. The two layers are separated by a deformable evaporation interface. A linear stability analysis is carried out to study the convective instability during evaporation. In previous works, the interface is assumed to be under equilibrium state. In contrast with previous works, we give up the equilibrium assumption and use Hertz-Knudsen's relation to describe the phase change under non-equilibrium state. The influence of Marangoni effect, gravitational effect, degree of non-equilibrium and the dynamics of the vapor on the instability are discussed.

I. Singular perturbation problems involving singular points and turning points. II. On the averaged Lagrangian technique for nonlinear dispersive waves

In Part I a class of linear boundary value problems is considered which is a simple model of boundary layer theory. The effect of zeros and singularities of the coefficients of the equations at the point where the boundary layer occurs is considered. The usual boundary layer techniques are still applicable in some cases and are used to derive uniform asymptotic expansions. In other cases it is shown that the inner and outer expansions do not overlap due to the presence of a turning point outside the boundary layer. The region near the turning point is described by a two-variable expansion. In these cases a related initial value problem is solved and then used to show formally that for the boundary value problem either a solution exists, except for a discrete set of eigenvalues, whose asymptotic behaviour is found, or the solution is non-unique. A proof is given of the validity of the two-variable expansion; in a special case this proof also demonstrates the validity of the inner and outer expansions.

Nonlinear dispersive wave equations which are governed by variational principles are considered in Part II. It is shown that the averaged Lagrangian variational principle is in fact exact. This result is used to construct perturbation schemes to enable higher order terms in the equations for the slowly varying quantities to be calculated. A simple scheme applicable to linear or near-linear equations is first derived. The specific form of the first order correction terms is derived for several examples. The stability of constant solutions to these equations is considered and it is shown that the correction terms lead to the instability cut-off found by Benjamin. A general stability criterion is given which explicitly demonstrates the conditions under which this cut-off occurs. The corrected set of equations are nonlinear dispersive equations and their stationary solutions are investigated. A more sophisticated scheme is developed for fully nonlinear equations by using an extension of the Hamiltonian formalism recently introduced by Whitham. Finally the averaged Lagrangian technique is extended to treat slowly varying multiply-periodic solutions. The adiabatic invariants for a separable mechanical system are derived by this method.

Non-linear dispersive waves with a small dissipation

The general theory of Whitham for slowly-varying non-linear wavetrains is extended to the case where some of the defining partial differential equations cannot be put into conservation form. Typical examples are considered in plasma dynamics and water waves in which the lack of a conservation form is due to dissipation; an additional non-conservative element, the presence of an external force, is treated for the plasma dynamics example. Certain numerical solutions of the water waves problem (the Korteweg-de Vries equation with dissipation) are considered and compared with perturbation expansions about the linearized solution; it is found that the first correction term in the perturbation expansion is an excellent qualitative indicator of the deviation of the dissipative decay rate from linearity.

A method for deriving necessary and sufficient conditions for the existence of a general uniform wavetrain solution is presented and illustrated in the plasma dynamics problem. Peaking of the plasma wave is demonstrated, and it is shown that the necessary and sufficient existence conditions are essentially equivalent to the statement that no wave may have an amplitude larger than the peaked wave.

A new type of fully non-linear stability criterion is developed for the plasma uniform wavetrain. It is shown explicitly that this wavetrain is stable in the near-linear limit. The nature of this new type of stability is discussed.

Steady shock solutions are also considered. By a quite general method, it is demonstrated that the plasma equations studied here have no steady shock solutions whatsoever. A special type of steady shock is proposed, in which a uniform wavetrain joins across a jump discontinuity to a constant state. Such shocks may indeed exist for the Korteweg-de Vries equation, but are barred from the plasma problem because entropy would decrease across the shock front.

Finally, a way of including the Landau damping mechanism in the plasma equations is given. It involves putting in a dissipation term of convolution integral form, and parallels a similar approach of Whitham in water wave theory. An important application of this would be towards resolving long-standing difficulties about the "collisionless" shock.

Coherent population transfer with chirped few-cycle laser pulses in an excited-doublet four-level system

The behavior of population transfer in an excited-doublet four-level system driven by linear polarized few-cycle ultrashort laser pulses is investigated numerically. It is shown that almost complete population transfer can be achieved even when the adiabatic criterion is not fulfilled. Moreover, the robustness of this scheme in terms of the Rabi frequencies and chirp rates of the pulses is explored.

Lasing without or with inversion in an open four-level system with a phase-fluctuation driving field

The effect of exit rate and the ratio of atomic injection rate on gain behaviour has been investigated, and the effects of phase fluctuation on absorption, dispersion and population difference in an open four-level system have been analysed by using numerical simulation from the steady linear, analytical solution. The variation of the linewidth, Rabi frequency of the driving field, the exit rate or the ratio of atomic injection rate can change the lasing properties in the open system. The presence of finite linewidth due to driving-field phase fluctuation prevents the open four-level atomic system from obtaining a high refractive index along with zero absorption.

High and stable conversion efficiency obtaining in single-stage multi-crystal optical parametric chirped pulse amplification system

An optical parametric chirped-pulse amplification system is demonstrated to provide 32.9% pump-to-signal conversion efficiency . Special techniques are used to make the signal and pump pulses match with each other in both spectral and temporal domains. The broadband 9.5-mJ pulses are produced at the repetition rate of 1 Hz with the gain of over 1.9 x 10(8). The output energy fluctuation of 7.8% is achieved for the saturated amplification process against the pump fluctuation of 10%.

Social Organisation of the Short-finned Pilot Whale, Globicephala macrorhynchus, with Special Reference to the Comparative Social Ecology of Delphinids

As a contribution to the understanding of comparative social trends within the cetacean family Delphinidae, a 22-month study was conducted on the shortfinned pilot whale, Globicephala macrorhynchus, which has been suggested to have a unique social system in which males and females in the same group are related and mating occurs outside of the group. The individual identification of 495 pilot whales, analysed in daily group association patterns, allowed identification of 46 pods. They were classified as productive or non-productive based on the presence or absence of immature animals. Productive pods were a significantly larger, although 12% of them lacked adult males. Two classes of whales (residents and visitors) were defined by patterns of occurrence,suggesting differential patterns of habitat use. Resident pods occasionally travelled together (41% of all groups) and associations between age and sex classes showed that in mixed-pod groups, the highest ranked associations of the reproductive females were with males from other pods, while within pods, adult males and females associated less. During summer, the proposed peak conception period, pilot whale groups were significantly larger and contained individuals from a significantly greater number of pods. These findings support the hypothesis that males and females mate when associating with individuals from other pods. A comparative analysis of sexual dimorphism, brain size, and testes size, habitat, prey and group size within the 17 delphinid genera identified a correlation between sexual dimorphism and body size, but relative measures of brain size and testes size did not correlate with broad ecological or social classifications. However, a comparison of three delphinid societies identified two distinct male mating systems: males of the small, mono-morphic Tursiops truncatus live in age/sex segregated groups and mate with a number of discrete female communities. Males in the large sexually dimorphic Glob icephala spp. and Orcinus orca mate with associated female pods and yet remain with their female kin. This corresponds to the avunculate social system described in some human societies. It could evolve from a promiscuous mating system where there is little guarantee of paternity and where males that live with their kin increase their inclusive fitness.

On the solution of first excursion problems by simulation with applications to probabilistic seismic performance assessment

In a probabilistic assessment of the performance of structures subjected to uncertain environmental loads such as earthquakes, an important problem is to determine the probability that the structural response exceeds some specified limits within a given duration of interest. This problem is known as the first excursion problem, and it has been a challenging problem in the theory of stochastic dynamics and reliability analysis. In spite of the enormous amount of attention the problem has received, there is no procedure available for its general solution, especially for engineering problems of interest where the complexity of the system is large and the failure probability is small.

The application of simulation methods to solving the first excursion problem is investigated in this dissertation, with the objective of assessing the probabilistic performance of structures subjected to uncertain earthquake excitations modeled by stochastic processes. From a simulation perspective, the major difficulty in the first excursion problem comes from the large number of uncertain parameters often encountered in the stochastic description of the excitation. Existing simulation tools are examined, with special regard to their applicability in problems with a large number of uncertain parameters. Two efficient simulation methods are developed to solve the first excursion problem. The first method is developed specifically for linear dynamical systems, and it is found to be extremely efficient compared to existing techniques. The second method is more robust to the type of problem, and it is applicable to general dynamical systems. It is efficient for estimating small failure probabilities because the computational effort grows at a much slower rate with decreasing failure probability than standard Monte Carlo simulation. The simulation methods are applied to assess the probabilistic performance of structures subjected to uncertain earthquake excitation. Failure analysis is also carried out using the samples generated during simulation, which provide insight into the probable scenarios that will occur given that a structure fails.

The role of sites of special scientific interest (SSSIs) in the conservation of British rivers

This paper discusses the particular contribution of the SSSI (Sites of Special Scientific Interest) as a way of nature conservation for rivers. In 1989, the Nature Conservancy Council proposed a dual selection system for selection of rivers; either (1) "Whole river" SSSIs representing the main types of river, or rivers which show classic and representative transitions down their lengths, or (2) "Sectional" SSSIs which are shorter stretches of river with high nature conservation interest. The NCC has recently classified all SSSIs with a river interest into 4 categories: - river SSSIs, river valley SSSIs, river adds interest - where the river clearly adds biological interest to the site, and rivers of incidental interest. The overall length of river SSSIs amounts to almost 1000 km.

Part I. Energy straggling of ^4He below 2.0 MeV in Al, Ni, Au and Pt. Part II. Studies of the Ti-W metallization system on Si

Part I.

In recent years, backscattering spectrometry has become an important tool for the analysis of thin films. An inherent limitation, though, is the loss of depth resolution due to energy straggling of the beam. To investigate this, energy straggling of ⁴He has been measured in thin films of Ni, Al, Au and Pt. Straggling is roughly proportional to square root of thickness, appears to have a slight energy dependence and generally decreases with decreasing atomic number of the adsorber. The results are compared with predictions of theory and with previous measurements. While Ni measurements are in fair agreement with Bohr's theory, Al measurements are 30% above and Au measurements are 40% below predicted values. The Au and Pt measurements give straggling values which are close to one another.

Part II.

MeV backscattering spectrometry and X-ray diffraction are used to investigate the behavior of sputter-deposited Ti-W mixed films on Si substrates. During vacuum anneals at temperatures near 700°C for several hours, the metallization layer reacts with the substrate. Backscattering analysis shows that the resulting compound layer is uniform in composition and contains Ti, Wand Si. The Ti:W ratio in the compound corresponds to that of the deposited metal film. X-ray analyses with Reed and Guinier cameras reveal the presence of the ternary Ti_xW_(1-x)Si₂ compound. Its composition is unaffected by oxygen contamination during annealing, but the reaction rate is affected. The rate measured on samples with about 15% oxygen contamination after annealing is linear, of the order of 0.5 Å per second at 725°C, and depends on the crystallographic orientation of the substrate and the dc bias during sputter-deposition of the Ti-W film.

Au layers of about 1000 Å thickness were deposited onto unreacted Ti-W films on Si. When annealed at 400°C these samples underwent a color change,and SEM micrographs of the samples showed that an intricate pattern of fissures which were typically 3µm wide had evolved. Analysis by electron microprobe revealed that Au had segregated preferentially into the fissures. This result suggests that Ti-W is not a barrier to Au-Si intermixing at 400°C.

Convex Relaxation for Low-Dimensional Representation: Phase Transitions and Limitations

There is a growing interest in taking advantage of possible patterns and structures in data so as to extract the desired information and overcome the curse of dimensionality. In a wide range of applications, including computer vision, machine learning, medical imaging, and social networks, the signal that gives rise to the observations can be modeled to be approximately sparse and exploiting this fact can be very beneficial. This has led to an immense interest in the problem of efficiently reconstructing a sparse signal from limited linear observations. More recently, low-rank approximation techniques have become prominent tools to approach problems arising in machine learning, system identification and quantum tomography.

In sparse and low-rank estimation problems, the challenge is the inherent intractability of the objective function, and one needs efficient methods to capture the low-dimensionality of these models. Convex optimization is often a promising tool to attack such problems. An intractable problem with a combinatorial objective can often be "relaxed" to obtain a tractable but almost as powerful convex optimization problem. This dissertation studies convex optimization techniques that can take advantage of low-dimensional representations of the underlying high-dimensional data. We provide provable guarantees that ensure that the proposed algorithms will succeed under reasonable conditions, and answer questions of the following flavor:

More specifically, i) Focusing on linear inverse problems, we generalize the classical error bounds known for the least-squares technique to the lasso formulation, which incorporates the signal model. ii) We show that intuitive convex approaches do not perform as well as expected when it comes to signals that have multiple low-dimensional structures simultaneously. iii) Finally, we propose convex relaxations for the graph clustering problem and give sharp performance guarantees for a family of graphs arising from the so-called stochastic block model. We pay particular attention to the following aspects. For i) and ii), we aim to provide a general geometric framework, in which the results on sparse and low-rank estimation can be obtained as special cases. For i) and iii), we investigate the precise performance characterization, which yields the right constants in our bounds and the true dependence between the problem parameters.