Approximating the single source unsplittable min-cost flow problem

In the single source unsplittable min-cost flow problem, commodities must be routed simultaneously from a common source vertex to certain destination vertices in a given graph with edge capacities and costs; the demand of each commodity must be routed along a single path so that the total flow through any edge is at most its capacity. Moreover, the total cost must not exceed a given budget. This problem has been introduced by Kleinberg [7] and generalizes several NP-complete problems from various areas in combinatorial optimization such as packing, partitioning, scheduling, load balancing, and virtual-circuit routing. Kolliopoulos and Stein [9] and Dinitz, Garg, and Goemans [4] developed algorithms improving the first approximation results of Kleinberg for the problem of minimizing the violation of edge capacities and for other variants. However, known techniques do not seem to be capable of providing solutions without also violating the cost constraint. We give the first approximation results with hard cost constraints. Moreover, all our results dominate the best known bicriteria approximations. Finally, we provide results on the hardness of approximation for several variants of the problem. Received: August 23, 2000 / Accepted: April 20, 2001?Published online October 2, 2001     

Enhanced four-wave mixing in mercury isotopes, prepared by stark-chirped rapid adiabatic passage

We demonstrate significant enhancement of four-wave mixing in coherently driven mercury isotopes to generate vacuum-ultraviolet radiation at 125 nm. The enhancement is accomplished by preparation of the mercury atoms in a state of maximum coherence, i.e. maximum nonlinear-optical polarization, driven by Stark-chirped rapid adiabatic passage (SCRAP). In this technique, a pump laser at 313 nm excites the two-photon transition between the ground state 6s²¹S₀ and the target state 7s ¹S₀ in mercury. A strong, off-resonant radiation field at 1064 nm generates dynamic Stark shifts. These Stark shifts serve to induce a rapid adiabatic passage process on the two-photon transition. During the process a coherent superposition of the two states is established, which enhances the nonlinear-optical polarization in the medium to the maximum possible value. The maximum coherence permits efficient four-wave mixing of a pump laser and an additional probe laser at 626 nm. The efficiency is further enhanced, as the SCRAP process allows to stimulate the complete set of different mercury isotopes to participate in the frequency conversion process. This enlarges the effective atomic density of the medium. Thus, we observe the generation of vacuum-ultraviolet radiation at 125 nm enhanced by more than one order of magnitude with respect to conventional frequency conversion. Parallel to the frequency conversion process, we monitored the evolution of the population in the medium by laser-induced fluorescence. These data demonstrate efficient coherent population transfer by SCRAP.     

Correlated and non-correlated growth kinetics of pentacene in the sub-monolayer regime

We present a study of the growth kinetics of pentacene monolayer islands on SiO₂ in the submonolayer regime by using Atomic Force Microscopy (AFM). Two distinct growth modes, namely correlated growth (CG) and non-correlated growth (NCG), have been identified by Voronoi tesselation. These two modes are characterized by different island growth kinetics. In the case of correlated growth, the average island size 〈A〉 scales with deposition time t i.e. 〈A〉 ∝ t whereas for non-correlated growth, 〈A〉 ∝ t². The CG and NCG regimes are defined by the level of re-evaporation which determines the capture zones around the islands: Wigner-Seitz cells for CG and coronas of width λ_D (λ_D is the mean diffusion distance on SiO₂ before re-evaporation) for NCG. A simple model is proposed to reproduce the experimental growth kinetics in both modes.     

Structural studies of Cr-doped mullite derived from single-phase precursors

Cr-doped mullites were prepared from single-phase precursors containing up to 9.60 wt% Cr₂O₃ using a sol-gel technique followed by thermal treatment. Particle induced X-ray emission spectroscopy and X-ray powder diffraction were used to characterize the samples. Mullites were orthorhombic, space group Pbam. Cr doping caused the increase of unit-cell parameters. Strongest expansion was noticed along c-axis followed by a and b (Δc/c=0.089, Δa/a=0.061, Δb/b=0.045% per mole Cr₂O₃). A second phase, namely θ-(Al,Cr)₂O₃, was revealed by XRD in the sample containing 9.60 wt% Cr₂O₃. The structure of mullites was refined by the Rietveld method, location of Cr³⁺ was performed by the EPR spectroscopy. At low chromium doping level (Cr₂O₃ content less than ∼5 wt%) Cr³⁺ ions were substituted for Al³⁺ in the AlO₆ octahedra of the mullite structure (M1 site). For higher doping level, Cr³⁺ ions were additionally substituted for Al³⁺ in the AlO₆ octahedra of the second phase [θ-(Al,Cr)₂O₃ at 1400 °C, or α-(Al,Cr)₂O₃ at 1600 °C] which segregated in the system. Substitution of Cr³⁺ for Al³⁺ on M1 site in the mullite structure resulted in increase of average distances in (M1)O₆ octahedron and decrease of average distances in T*O₄ tetrahedron, while average distances in TO₄ tetrahedron stayed almost constant.     

Studies on pre-hump and main fractions of cellulose-2,5-acetate in acetone

Technical cellulose-2.5-acetates (CA 2.5) were characterized regarding their carbohydrate composition in comparison to the raw material. The association of the CA 2.5 samples in acetone was studied by size exclusion chromatography (SEC) using various acetone grades and styrene divinylbenzene copolymer columns. In HPLC grade acetone with and without addition of 1% water up to three different pre-humps eluted in front of the main fraction of the polymer. The evaluation of the main peak by light scattering measurements resulted in high molar masses indicating that for these technical CA 2.5 samples even the main fraction is not dissolved without association. No pre-humps or association phenomena were observed after addition of 1 ppm LiBr to HPLC grade acetone or with p.a. grade acetone. In addition pre-hump enriched and pre-hump free fractions were isolated by fractionated precipitation. The carbohydrate composition of these fractions was determined and correlated with their association pattern in SEC investigations.     

Indecomposable modules over the Virasoro Lie algebra and a conjecture of V. Kac

We consider a class of indecomposable modules over the Virasoro Lie algebra that we call bounded admissible modules. We get results concerning the center and the dimensions of the weight spaces. We prove that these modules always contain a submodule with one-dimensional weight spaces. From this follows the proof of a conjecture of V. Kac concerning the classification of simple admissible modules.Preprint Université de Bourgogne-mai 1990     

A cutting plane algorithm for a clustering problem

In this paper we consider a clustering problem that arises in qualitative data analysis. This problem can be transformed to a combinatorial optimization problem, the clique partitioning problem. We have studied the latter problem from a polyhedral point of view and determined large classes of facets of the associated polytope. These theoretical results are utilized in this paper. We describe a cutting plane algorithm that is based on the simplex method and uses exact and heuristic separation routines for some of the classes of facets mentioned before. We discuss some details of the implementation of our code and present our computational results. We mention applications from, e.g., zoology, economics, and the political sciences.     

Atomistic packing models for experimentally investigated swelling states induced by CO2 in glassy polysulfone and poly(ether sulfone)

Atomistic packing models have been created, which help to better understand the experimentally observed swelling behavior of glassy polysulfone and poly (ether sulfone), under CO₂ gas pressures up to 50 bar at 308 K. The experimental characterization includes the measurement of the time‐dependent volume dilation of the polymer samples after a pressure step and the determination of the corresponding gas concentrations by gravimetric gas‐sorption measurements. The models obtained by force‐field‐based molecular mechanics and molecular dynamics methods allow a detailed atomistic analysis of representative swelling states of polymer/gas systems, with respect to the dilation of the matrix. Also, changes of free volume distribution and backbone mobility are accessible. The behavior of gas molecules in unswollen and swollen polymer matrices is characterized in terms of sorption, diffusion, and plasticization. © 2006 Wiley Periodicals, Inc. J Polym Sci Part B: Polym Phys 44: 1874–1897, 2006