Approximation Algorithms for Network Design and Orienteering

This thesis presents approximation algorithms for some NP-Hard combinatorial optimization problems on graphs and networks; in particular, we study problems related to Network Design. Under the widely-believed complexity-theoretic assumption that P is not equal to NP, there are no efficient (i.e., polynomial-time) algorithms that solve these problems exactly. Hence, if one desires efficient algorithms for such problems, it is necessary to consider approximate solutions: An approximation algorithm for an NP-Hard problem is a polynomial time algorithm which, for any instance of the problem, finds a solution whose value is guaranteed to be within a multiplicative factor of the value of an optimal solution to that instance. We attempt to design algorithms for which this factor, referred to as the approximation ratio of the algorithm, is as small as possible. The field of Network Design comprises a large class of problems that deal with constructing networks of low cost and/or high capacity, routing data through existing networks, and many related issues. In this thesis, we focus chiefly on designing fault-tolerant networks. Two vertices u,v in a network are said to be k-edge-connected if deleting any set of k − 1 edges leaves u and v connected; similarly, they are k-vertex connected if deleting any set of k − 1 other vertices or edges leaves u and v connected. We focus on building networks that are highly connected, meaning that even if a small number of edges and nodes fail, the remaining nodes will still be able to communicate. A brief description of some of our results is given below. We study the problem of building 2-vertex-connected networks that are large and have low cost. Given an n-node graph with costs on its edges and any integer k, we give an O(log n log k) approximation for the problem of finding a minimum-cost 2-vertex-connected subgraph containing at least k nodes. We also give an algorithm of similar approximation ratio for maximizing the number of nodes in a 2-vertex-connected subgraph subject to a budget constraint on the total cost of its edges. Our algorithms are based on a pruning process that, given a 2-vertex-connected graph, finds a 2-vertex-connected subgraph of any desired size and of density comparable to the input graph, where the density of a graph is the ratio of its cost to the number of vertices it contains. This pruning algorithm is simple and efficient, and is likely to find additional applications. Recent breakthroughs on vertex-connectivity have made use of algorithms for element-connectivity problems. We develop an algorithm that, given a graph with some vertices marked as terminals, significantly simplifies the graph while preserving the pairwise element-connectivity of all terminals; in fact, the resulting graph is bipartite. We believe that our simplification/reduction algorithm will be a useful tool in many settings. We illustrate its applicability by giving algorithms to find many trees that each span a given terminal set, while being disjoint on edges and non-terminal vertices; such problems have applications in VLSI design and other areas. We also use this reduction algorithm to analyze simple algorithms for single-sink network design problems with high vertex-connectivity requirements; we give an O(k log n)-approximation for the problem of k-connecting a given set of terminals to a common sink. We study similar problems in which different types of links, of varying capacities and costs, can be used to connect nodes; assuming there are economies of scale, we give algorithms to construct low-cost networks with sufficient capacity or bandwidth to simultaneously support flow from each terminal to the common sink along many vertex-disjoint paths. We further investigate capacitated network design, where edges may have arbitrary costs and capacities. Given a connectivity requirement R_uv for each pair of vertices u,v, the goal is to find a low-cost network which, for each uv, can support a flow of R_uv units of traffic between u and v. We study several special cases of this problem, giving both algorithmic and hardness results. In addition to Network Design, we consider certain Traveling Salesperson-like problems, where the goal is to find short walks that visit many distinct vertices. We give a (2 + epsilon)-approximation for Orienteering in undirected graphs, achieving the best known approximation ratio, and the first approximation algorithm for Orienteering in directed graphs. We also give improved algorithms for Orienteering with time windows, in which vertices must be visited between specified release times and deadlines, and other related problems. These problems are motivated by applications in the fields of vehicle routing, delivery and transportation of goods, and robot path planning.

Revitalização dos saberes e práticas Kaingang sobre as plantas tradicionais como proposta de educação ambiental na terra indígena Ligeiro

O presente trabalho objetiva investigar a Revitalização dos Saberes e Práticas Kaingang Sobre as Plantas Tradicionais como Proposta de Educação Ambiental na comunidade Terra Indígena de Ligeiro no município de Charrua - RS. Trata-se de uma pesquisa de campo que busca melhor compreender o que provocou o abandono e esquecimento desses saberes, bem como possíveis alternativas teóricas e práticas para que a revitalização dos saberes culturais ancestrais seja realizada. Justifica-se pelo fato da utilização de plantas medicinais para o tratamento de enfermidades estar enraizada nas culturas indígenas e poder assim suprir, em parte, a deficiente atenção à saúde e as realidades da fome em muitas T.I. Foram realizadas visitas a campo para análise da situação atual e coleta de informações, com aplicação de entrevistas com vários indígenas, bem como com kujà e curandeiras; se implantou um horto medicinal com várias plantas, ervas e se distribuíram mudas de plantas frutíferas nativas. Para este projeto, dois alunos indígenas do IFRS - Campus Sertão atuaram na implantação deste Horto, assim como outros alunos indígenas da Escola Estadual Indígena de Ensino Médio Fág Mág (Pinheiro Grande) trabalharam e apoiaram na execução dessa ação. Através da realização de fotos e vídeos, foram analisadas também as expressões atuais da cultura Kaingang na conjuntura, os elementos significativos que estão guardados ao longo das gerações e apontamos os desafios de permanecer na comunidade e revitalizar com sustentabilidade os saberes e práticas Kaingang, sempre com um olhar incondicional pela natureza. Foram sistematizadas as denominações específicas da cada planta, em correspondência com seu nome científico e com o seu nome tradicional da cosmologia dual Kaingang (kam e kanhru). Conclui-se a partir dessa investigação que houve efetivamente o abandono e a falta de valorização de saberes e práticas relacionadas com a educação ambiental, pelas pressões da sociedade branca, o desejo de alguns indígenas de ser moderno e aceito na sociedade branca e pela ausência de trabalho de um educador ambiental. As iniciativas de revitalização são possíveis; o uso de plantas e alimentos tradicionais estão relacionadas com atividades que precisam ser vivenciadas primordialmente na escola, na relação com os kujà tradicionais e no desenvolvimento de projetos específicos e na motivação permanente para a responsabilidade ambiental, preservando a cultura e os costumes Kaingang que ainda são preciosos, especialmente na promoção da saúde da comunidade

Characterization of Copper Covetic Bulk and Films: Copper with High Carbon Content

Incorporation of carbon nanostructures in metals is desirable to combine the strongly bonded electrons in the metal and the free electrons in carbon nanostructures that give rise to high ampacity and high conductivity, respectively. Carbon in copper has the potential to impact industries such as: building construction, power generation and transmission, and microelectronics. This thesis focuses on the structure and properties of bulk and thin films of a new material, Cu covetic, that contains carbon in concentrations up to 16 at.%. X-ray photoelectron spectroscopy (XPS) shows C 1s peak with both sp2 and sp3 bonded C measuring up to 3.5 wt.% (16 at.%). High resolution transmission electron microscopy and electron diffraction of bulk covetic samples show a modulated structure of ≈ 1.6 nm along several crystallographic directions in regions that have high C content suggesting that the carbon incorporates into the copper lattice forming a network. Electron energy loss spectra (EELS) from covetics reveal that the level of graphitization from the source material, activated carbon, is maintained in the covetic structure. Bulk Cu covetics have a slight increase in the lattice constant, as well as <111> texturing, or possibly a different structure, compared to pure Cu. Density functional theory calculations predict bonding between C and Cu at the edges and defects of graphene sheets. The electrical resistivity of bulk covetics first increases and then decreases with increasing C content. Cu covetic films were deposited using e-beam and pulsed laser deposition (PLD) at different temperatures. No copper oxide or any allotropes of carbon are present in the films. The e-beam films show enhanced electrical and optical properties when compared to pure Cu films of the same thickness even though no carbon was detected by XPS or EELS. They also have slightly higher ampacity than Cu metal films. EELS analysis of the C-K-edge in the PLD films indicate that graphitic carbon is transferred from the bulk into the films with uniform carbon distribution. PLD films exhibit flatter and higher transmittance curves and sheet resistance two orders of magnitude lower than e-beam films leading to a high figure of merit as transparent conductors.

Phase diagram of the system Ca-Ti-O at 1200 K

Phase relations in the system Ca-Ti-O have been established by equilibration of several samples at 1200 K for prolonged periods and identification of phases in quenched samples by optical and scanning electron microscopy, XRD and EDS. Samples representing 20 compositions in the ternary system were analyzed. There was negligible solid solubility of Ca in the phases along the binary Ti-O, and of Ti in CaO. Four ternary oxides were identified: CaTiO3, Ca4Ti3O10 and Ca3Ti2O7 containing tetravalent titanium, and CaTi2O4 containing trivalent titanium. Tie-lines link calcium titanite (CaTi2O4) with the three calcium titanates (CaTiO3, Ca4Ti3O10 and Ca3Ti2O7), CaO, oxygen excess TiO1+delta and stoichiometric TiO. Tie-lines connect CaTiO3 with TiO2-x, Magneli phases TinO2n-1 (28 >= n >= 4), Ti3O5, Ti2O3 and TiO1+delta. CaO was found to coexist with TiO, and Ti-O solid solutions alpha and beta. The phase diagram is useful for understanding the mechanisms and kinetics of direct calciothermic reduction of TiO2 to metal and electrochemical reduction of TiO2 using graphite anode and molten CaCl2 electrolyte.

Chemical-shift of the X-ray K-absorption edge of Co in some compounds, complexes and minerals

The chemical-shift of the X-ray K-absorption edge of Co was studied in a large number of compounds, complexes (spinels) and minerals of Co in its different oxidation states having widely different crystal structures and containing different types of bonding and various types of ligands, and were reported collectively, for the first time, in a single paper. A quadratic relationship was established on the basis of least-squares regression analysis to hold between the chemical-shift and the effective charge on the absorbing atom, but the dominance of the linear term was shown. This relation was utilized in evaluating the charge on the Co-ion in a number of minerals. The effect on chemical-shift of oxidation states of the absorbing atom, of the bond length, crystal structure and higher shell atoms of the molecule, and of electronegativity, atomic number and ionic radius of the ligand was discussed.

High-Temperature (1023 K to 1273 K 750 degrees C to 1000 degrees C]) Plastic Deformation Behavior of B-Modified Ti-6Al-4V Alloys: Temperature and Strain Rate Effects

A minor addition of B to the Ti-6Al-4V alloy, by similar to 0.1 wt pct, reduces its as-cast prior beta grain size by an order of magnitude, whereas higher B content leads to the presence of in situ formed TiB needles in significant amounts. An experimental investigation into the role played by these microstructural modifications on the high-temperature deformation behavior of Ti-6Al-4V-xB alloys, with x varying between 0 wt pct and 0.55 wt pct, was conducted. Uniaxial compression tests were performed in the temperature range of 1023 K to 1273 K (750 degrees C to 1000 degrees C) and in the strain rate range of 10(-3) to 10(+1) s(-1). True stress-true strain responses of all alloys exhibit flow softening at lower strain rates and oscillations at higher strain rates. The flow softening is aided by the occurrence of dynamic recrystallization through lath globularization in high temperature (1173 K to 1273 K 900 degrees C to 1000 degrees C]) and a lower strain rate (10(-2) to 10(-3) s(-1)) regime. The grain size refinement with the B addition to Ti64, despite being marked, had no significant effect on this. Oscillations in the flow curve at a higher strain rate (10(0) to 10(+1) s(-1)), however, are associated with microstructural instabilities such as bending of laths, breaking of lath boundaries, generation of cavities, and breakage of TiB needles. The presence of TiB needles affected the instability regime. Microstructural evidence suggests that the matrix cavitation is aided by the easy fracture of TiB needles.

Chemical Shift of the X-Ray K-Absorption Edge of Cu in Some of Its Compounds, Complexes and Superconductors

Chemical shifts, ΔE, of the X-ray K-absorption edge in several compounds, complexes of copper including its superconducting oxides possessing formal oxidation states +1 and +2 have been measured. It has been shown that the chemical shift is primarily governed by the effective ionic charge on the absorbing ion and the nature of the atoms in the first coordination shell around the absorbing ion. The relation between the chemical shift, ΔE , and the effective charge q on the absorbing ion is found to be ΔE=Aq+Bq2+Cq3+Dq4 (A, B, C and D are constants). The effects of electronegativity, atomic number, oxidation state, crystal structure, the valence d-orbital electrons, etc. on the X-ray absorption chemical shift have been discussed. ©1990 The Physical Society of Japan

Flow Instabilities and fracture in Ti-6Al-4V deformed in compression at 298 K to 673 K

Uniaxial compression tests were conducted on Ti-6Al-4V specimens in the strain-rate range df 0.001 to 1 s(-1) and temperature range of 298 to 673 K. The stress-strain curves exhibited a peak flow stress followed by flow softening. Up to 523 K, the specimens cracked catastrophically after the flow softening started. Adiabatic shear banding was observed in this regime. The fracture surface exhibited both mode I and II fracture features. The state of stress existing in a compression test specimen when bulging occurs is responsible for this fracture. The instabilities observed in the present tests are classified as ''geometric'' in nature and are state-of-stress dependant, unlike the ''intrinsic'' instabilities, which are dependant on the dynamic constitutive behavior of the material.

Coherent phonons in pyrochlore titanates A(2)Ti(2)O(7) (A = Dy, Gd, Tb): A phase transition in Dy2Ti2O7 at 110 K

We study the generation of coherent optical phonons in spin-frustrated pyrochlore single crystals Dy2Ti2O7, Gd2Ti2O7, and Tb2Ti2O7 using femtosecond laser pulses (65 fs, 1.57 eV) in degenerate time-resolved transmission experiments as a function of temperature from 4 to 296 K. At 4 K, two coherent phonons are observed at similar to 5.3 THz (5.0 THz) and similar to 9.3 THz (9.4 THz) for Dy2Ti2O7 (Gd2Ti2O7), whereas three coherent phonons are generated at similar to 5.0, 8.6, and 9.7 THz for Tb2Ti2O7. In the case of spin-ice Dy2Ti2O7, a clear discontinuity is observed in the linewidths of both the coherent phonons as well as in the phase of lower-energy coherent phonon mode, indicating a subtle structural change at 110 K. Another important observation is a phase difference of pi between the modes in all the samples, thus suggesting that the driving forces behind the generation of these modes could be different in nature, unlike a purely impulsive or displacive mechanism.

Theoretical analysis of x-ray-absorption near-edge fine structure at the O and metal K edges of LaFeO3 and LaCoO3

We present experimental x-ray-absorption spectra at the oxygen and 3d transition-metal K edges of LaFeO3 and LaCoO3. We interpret the experimental results in terms of detailed theoretical calculations based on multiple-scattering theory. Along with providing an understanding of the origin of various experimental features, we investigate the effects of structural distortions and the core-hole potential in determining the experimental spectral shape. The results indicate that the core-hole potential as well as many-body effects within the valence electrons do not have any strong effect on the spectra suggesting that the spectral features can be directly interpreted in terms of the electronic structure of such compounds.

Anomalous temperature dependence of phonons and photoluminescence bands in pyrochlore Er(2)Ti(2)O(7): signatures of structural deformation at 130 K

We report a Raman study of single crystal pyrochlore Er(2)Ti(2)O(7) as a function of temperature from 12 to 300 K. In addition to the phonons, various photoluminescence (PL) lines of Er(3+) in the visible range are also observed. Our Raman data show an anomalous red-shift of two phonons (one at similar to 200 cm(-1) and another at similar to 520 cm(-1)) upon cooling from room temperature which is attributed to phonon-phonon anharmonic interactions. However, the phonons at similar to 310, 330, and 690 cm(-1) initially show a blue-shift upon cooling from room temperature down to about 130 K, followed by a red-shift, indicating a structural deformation at similar to 130 K. The intensities of the PL bands associated with the transitions between the various levels of the ground state manifold ((4)I(15/2)) and the (2)H(11/2) as well as (4)S(3/2) excited state manifolds of Er(3+) show a change at similar to 130 K. Moreover, the temperature dependence of the peak position of the two PL bands shows a change in their slope (d(omega)/d(T)) at similar to 130 K, thus further strengthening the proposal of a structural deformation. The temperature dependence of the peak positions of the PL bands has been analyzed using the theory of optical dephasing in crystals.

Anomalous scattering factor determined by semicircle fitting near the K-absorption edge of Ge

It is shown that the locus of the f' + if '' plot in the complex plane, f' being determined from measured f '' by using the dispersion relation, looks like a semicircle very near the absorption edge of Ge. The semicircular locus is derived from a quantum theory of X-ray resonant scattering when there is a sharp isolated peak in f '' just above the K-absorption edge. Using the semicircular behavior, an approach is proposed to determine the anomalous scattering factors in a crystal by fitting known calculated values based on an isolated-atom model to a semicircular focus. The determined anomalous scattering factors f' show excellent agreement with the measured values just below the absorption edge. In addition, the phase determination of a crystal structure factor has been considered by using the semicircular behavior.

K alpha yields from Ti foils irradiated with ultrashort laser pulses

We have studied the emission of Kalpha radiation from Ti foils irradiated with ultrashort (45 fs) laser pulses. We utilized the fundamental (800 nm) light from a Ti:sapphire laser on bare foils and foils coated with a thin layer of parylene E (CH). The focusing was varied widely to give a range of intensities from approximately 10(15)-10(19) W cm(-2). Our results show a conversion efficiency of laser to Kalpha energy of similar to 10(-4) at tight focus for both types of targets. In addition, the coated targets exhibited strong secondary peaks of conversion at large defocus, which we believe are due to modification of the extent of preformed plasma due to the dielectric nature of the plastic layer. This in turn affects the level of resonance absorption. A simple model of Kalpha production predicts a much higher conversion than seen experimentally and possible reasons for this are discussed.