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.

Programa ciclovida como política de mobilidade urbana sustentável: estudo empírico na Universidade Federal do Paraná

The urban mobility has in the bicycle its symbol of the most environmentally sustainable modal of transportation of the planet, title conferred by the United Nations Organization (ONU). Nevertheless, the cities suffer with the traffic jam caused by the automobile fleet growth, what implies in a larger displacement time, injuries to the environment, to financials and to the quality of life. In order to build in a sustainable way the urban mobility, public policies are necessary to encourage the preferential usage, by the society, of the mass transit or the non-motorized type of transportation. Objecting cooperate with the public power and the civil society, this study intents to, through an analysis about the UFPR Extension Program - CICLOVIDA, propose a sustainable urban mobility public policy development, with emphasis in the bicycle´s usage. eferentially, it is discussed concepts such as Society, State and Government as well as public policies, which go in cycles to the State´s and Government´s responsibilities; and are presented the Sustainable Urban Mobility Public Policies (PPMUS) in Brazil. Also, it is debated about the transport by bicycle as an option to the sustainable mobility. Methodologically, the study is of an empiric-social nature, with the application of both qualitative and observational methods, what characterizes as an exploratory level of research, with the researcher´s involvement in the participant form, due to her acting on the Program. Regarding the research lineation, it was used the bibliographic and documental form as well as case study, by means of the nonparametric sampling by accessibility or convenience. Related to the data collection technique, it was used structured interviews with self-applied questionnaires and natural participant observation. Aligned with the research´s objective and matter, the outcome confirmed that the Extension Program CICLOVIDA of the Federal University of Paraná (UFPR) may effectively contribute in the development of a PPMUS proposal with emphasis in the bicycle usage. Thus, it was built a political proposal with a free form writing, objecting subsidize policies both institutional as public MUS through the bicycle usage and therefore, support the mobility, also contributing to the sustainability and to the public development planning.

Geothermal district heating networks: modelling novel operational strategies incorporating heat storage

The value of integrating a heat storage into a geothermal district heating system has been investigated. The behaviour of the system under a novel operational strategy has been simulated focusing on the energetic, economic and environmental effects of the new strategy of incorporation of the heat storage within the system. A typical geothermal district heating system consists of several production wells, a system of pipelines for the transportation of the hot water to end-users, one or more re-injection wells and peak-up devices (usually fossil-fuel boilers). Traditionally in these systems, the production wells change their production rate throughout the day according to heat demand, and if their maximum capacity is exceeded the peak-up devices are used to meet the balance of the heat demand. In this study, it is proposed to maintain a constant geothermal production and add heat storage into the network. Subsequently, hot water will be stored when heat demand is lower than the production and the stored hot water will be released into the system to cover the peak demands (or part of these). It is not intended to totally phase-out the peak-up devices, but to decrease their use, as these will often be installed anyway for back-up purposes. Both the integration of a heat storage in such a system as well as the novel operational strategy are the main novelties of this thesis. A robust algorithm for the sizing of these systems has been developed. The main inputs are the geothermal production data, the heat demand data throughout one year or more and the topology of the installation. The outputs are the sizing of the whole system, including the necessary number of production wells, the size of the heat storage and the dimensions of the pipelines amongst others. The results provide several useful insights into the initial design considerations for these systems, emphasizing particularly the importance of heat losses. Simulations are carried out for three different cases of sizing of the installation (small, medium and large) to examine the influence of system scale. In the second phase of work, two algorithms are developed which study in detail the operation of the installation throughout a random day and a whole year, respectively. The first algorithm can be a potentially powerful tool for the operators of the installation, who can know a priori how to operate the installation on a random day given the heat demand. The second algorithm is used to obtain the amount of electricity used by the pumps as well as the amount of fuel used by the peak-up boilers over a whole year. These comprise the main operational costs of the installation and are among the main inputs of the third part of the study. In the third part of the study, an integrated energetic, economic and environmental analysis of the studied installation is carried out together with a comparison with the traditional case. The results show that by implementing heat storage under the novel operational strategy, heat is generated more cheaply as all the financial indices improve, more geothermal energy is utilised and less fuel is used in the peak-up boilers, with subsequent environmental benefits, when compared to the traditional case. Furthermore, it is shown that the most attractive case of sizing is the large one, although the addition of the heat storage most greatly impacts the medium case of sizing. In other words, the geothermal component of the installation should be sized as large as possible. This analysis indicates that the proposed solution is beneficial from energetic, economic, and environmental perspectives. Therefore, it can be stated that the aim of this study is achieved in its full potential. Furthermore, the new models for the sizing, operation and economic/energetic/environmental analyses of these kind of systems can be used with few adaptations for real cases, making the practical applicability of this study evident. Having this study as a starting point, further work could include the integration of these systems with end-user demands, further analysis of component parts of the installation (such as the heat exchangers) and the integration of a heat pump to maximise utilisation of geothermal energy.

Distribuição de conteúdos em redes veiculares usando mecanismos de comunicação tolerantes ao atraso

The last couple of decades have been the stage for the introduction of new telecommunication networks. It is expected that in the future all types of vehicles, such as cars, buses and trucks have the ability to intercommunicate and form a vehicular network. Vehicular networks display particularities when compared to other networks due to their continuous node mobility and their wide geographical dispersion, leading to a permanent network fragmentation. Therefore, the main challenges that this type of network entails relate to the intermittent connectivity and the long and variable delay in information delivery. To address the problems related to the intermittent connectivity, a new concept was introduced – Delay Tolerant Network (DTN). This architecture is built on a Store-Carry-and-Forward (SCF) mechanism in order to assure the delivery of information when there is no end-to-end path defined. Vehicular networks support a multiplicity of services, including the transportation of non-urgent information. Therefore, it is possible to conclude that the use of a DTN for the dissemination of non-urgent information is able to surpass the aforementioned challenges. The work developed focused on the use of DTNs for the dissemination of non-urgent information. This information is originated in the network service provider and should be available on mobile network terminals during a limited period of time. In order to do so, four different strategies were deployed: Random, Least Number of Hops First (LNHF), Local Rarest Bundle First (LRBF) e Local Rarest Generation First (LRGF). All of these strategies have a common goal: to disseminate content into the network in the shortest period of time and minimizing network congestion. This work also contemplates the analysis and implementation of techniques that reduce network congestion. The design, implementation and validation of the proposed strategies was divided into three stages. The first stage focused on creating a Matlab emulator for the fast implementation and strategy validation. This stage resulted in the four strategies that were afterwards implemented in the DTNs software Helix – developed in a partnership between Instituto de Telecomunicac¸˜oes (IT) and Veniam R , which are responsible for the largest operating vehicular network worldwide that is located in Oporto city. The strategies were later evaluated on an emulator that was built for the largescale testing of DTN. Both emulators account for vehicular mobility based on information previously collected from the real platform. Finally, the strategy that presented the best overall performance was tested on a real platform – in a lab environment – for concept and operability demonstration. It is possible to conclude that two of the implemented strategies (LRBF and LRGF) can be deployed in the real network and guarantee a significant delivery rate. The LRBF strategy has the best performance in terms of delivery. However, it needs to add a significant overhead to the network in order to work. In the future, tests of scalability should be conducted in a real environment in order to confirm the emulator results. The real implementation of the strategies should be accompanied by the introduction of new types of services for content distribution.

NFL-lipid nanocapsules for brain neural stem cell targeting in vitro and in vivo

International audience

Niosomes as Nanoparticular Drug Carriers: Fundamentals and Recent Applications

Drug delivery systems are defined as formulations aiming for transportation of a drug to the desired area of action within the body. The basic component of drug delivery systems is an appropriate carrier that protects the drug from rapid degradation or clearance and thereby enhances drug concentration in target tissues. Based on their biodegradable, biocompatible, and nonimmunogenic structure, niosomes are promising drug carriers that are formed by self-association of nonionic surfactants and cholesterol in an aqueous phase. In recent years, numerous research articles have been published in scientific journals reporting the potential of niosomes to serve as a carrier for the delivery of different types of drugs. The present review describes preparation methods, characterization techniques, and recent studies on niosomal drug delivery systems and also gives up to date information regarding recent applications of niosomes in drug delivery.

PPARα regulates endothelial progenitor cell maturation and myeloid lineage differentiation through a NADPH oxidase-dependent mechanism in mice

International audience

Transporte de juvenis de curimbatá Prochilodus lineatus em diferentes densidades

Transportation of curimbata Prochilodus lineatus juveniles in different densities. Tins study evaluated the effects of curimbata Prochilodus lineatus transportation in three densities (100, 150 and 250 g L-1) on survival, metabolic, ionic and hematological (red series) variables Curimbata juveniles were transported in plastic bag during six hours, and sampled before packing, immediately after die arrival, 24 and 96 hours after transportation During recovery, higher mortality was seen in fish transported in die highest density Water variables, such as conductivity and total ammonia, presented increased values as density increased (p < 005). whereas the opposite occurred with dissolved oxygen Glucose level observed in the arrival was high, significantly reducing after 96 hours Among ionic variables, chloride decreased in higher fish densities and according to sampling times Red series hematological variables, such as hematocrit, red blood cell and hemoglobin, Increased in arrival, but diminished 96 hours after transportation There were no significant differences in the interaction between density and time of sampling for mentioned variables 250 g L-1 density induced the highest mortality rate and the worst variables values measured 96 hours of recovery after the stressing event was enough to return to initial values for hematological variables, but was not sufficient to return to initial values for metabolic and ionic variables.

Dificuldades do enfermeiro no transporte secundário do doente crítico

Dada a tendência da centralização dos meios de diagnóstico e terapêutica com elevado nível de diferenciação, o transporte inter-hospitalar do doente em estado crítico torna-se cada vez mais frequente e fundamental na resposta adequada às suas necessidades. Contudo e porque se trata de doentes com risco eminente de vida, o transporte acarreta riscos para os quais o enfermeiro e restante equipa interdisciplinar devem estar despertos e preparados. O presente trabalho de investigação visa conhecer as dificuldades dos enfermeiros no transporte inter-hospitalar do doente crítico, no sentido de melhorar a sua intervenção minimizando os riscos reais e potenciais. A estratégia metodológica inicial adotada, para o enquadramento teórico, foi a pesquisa eletrónica de artigos científicos com qualidade metodológica, que decorreu de 6.12.2013 a 9.9.2014. Realizou-se um estudo quantitativo, transversal, correlacional que integrou também a construção/validação de um instrumento/escala para mensurar as dificuldades no transporte secundário (inter-hospitalar) do doente crítico percecionadas pelos enfermeiros (tamanho da amostra = 123). Nos principais resultados destaca-se que os enfermeiros percecionam dificuldades no transporte secundário do doente crítico (M=2,68;DP=0,65).Dentro das dificuldades são as relacionadas com os Recursos e instabilidade do doente (M=3,19;DP=0,77) e com a Morte do doente (M=2,73;DP=1,49) as mais auto reportadas sendo as relacionadas com o Planeamento do transporte secundário e os Sintomas fisiológicos vivenciados pelos enfermeiros as menos percecionadas. Os resultados indiciam também que a perceção das dificuldades diminui à medida que aumenta a experiência profissional nomeadamente nos fatores F1- Planeamento do transporte secundário e F2 -Recursos e instabilidade do doente e as dificuldades percecionadas no fator Planeamento do transporte secundário (F1) aumentam com a existência de formação específica na área.

Executive order no. 2016-29

This executive order by Governor Nikki R. Haley declares schools and government offices to be closed in certain counties beginning Wednesday, October 5, 2016 in order to support evacuation operations and mass transportation of the public with critical transportation needs due to Hurricane Matthew..

¿Se encuentran protegidas las esposas o compañeras menores de 15 años de los miembros de las partes en un conflicto armado no internacional frente a la violencia sexual ejercida por sus propias parejas o por otros miembros del grupo al que pertenecen?

La protección general atribuida en los conflictos armados no internacionales por el artículo 3 común a la población civil, de la que las niñas menores de 15 años forman parte, no depende de su filiación con alguna de las partes en el conflicto, y se extiende, en principio, a todos los actos de violencia, entre los que se encuentran los de naturaleza sexual cometidos por cualquiera de las mismas, incluyendo aquellos cometidos por los miembros de la parte en el conflicto con la que se encuentren afiliadas. Los casos contra Thomas Lubanga y Bosco Ntaganda muestran que, como regla general, las niñas menores de 15 años no desarrollan de manera prolongada actividades de participación directa en las hostilidades, por lo que, a pesar de acompañar permanente al grupo y de ser “esposas” o “compañeras” de sus comandantes, no asumen una función continua de combate y no pueden ser consideradas como miembros del mismo. Además, los actos de naturaleza sexual coercitivamente desarrollados por las niñas menores de 15 años reclutadas por las FPLC en favor de los comandantes y miembros del grupo con las que se encuentran esposadas, no cumple ninguno de los tres requisitos exigidos por el concepto de participación directa en las hostilidades porque: (a) no son idóneos para causar directamente por sí mismos el umbral de daño requerido; (b) no forman parte integral de ninguna operación militar que pudiera generar dicho umbral de daño; y (c) no poseen el nexo beligerante requerido, puesto que no están específicamente diseñados para causar un menoscabo a la parte adversa de las FLPC. Tampoco las demás actividades desarrolladas por las niñas menores de 15 años alistadas o reclutadas por las FLPC, incluyendo trabajo doméstico (donde principalmente desempeñaron tareas culinarias), transporte de comida a bases aéreas y acompañamiento a las esposas de los comandantes, cumplen, según la Sala de Primera Instancia I en el caso Lubanga, con los tres requisitos necesarios para su consideración como participación directa en las hostilidades. De ahí, que las niñas no hayan perdido en ningún momento su protección general. A todo lo anterior hay que añadir que los niños y niñas menores de 15 años, al ser una población particularmente vulnerable, gozan de una especial protección durante los conflictos armados (con independencia de su naturaleza), tal y como se manifiesta en la Convención de los Derechos del Niño de 1989, los Convenios de Ginebra de 1949 y de sus Protocolos adicionales de 1977, el Estatuto de la Corte Penal Internacional de 1998 y las Resoluciones 1882 de 2009, 1960 de 2010 y 2106 de 2013 del Consejo de Seguridad de las Naciones Unidas. Esta protección especial se extiende a los actos de violencia sexual cometidos por los miembros de las fuerzas armadas nacionales o grupos armados organizados que los alistan o reclutan. En consecuencia, la protección general y especial a que son acreedoras las niñas menores de 15 años, no se limita a las agresiones provenientes de las partes adversas en el conflicto, sino que se extiende también a la violencia sexual ejercida contra ellas por los miembros del propio grupo que las alistó o reclutó, incluso en el caso de que ésta sea ejercida por los comandantes que las tomaron como esposas o compañeras. Las niñas menores de 15 años alistadas o reclutadas entre 2002 y 2003 por las FPLC de Thomas Lubanga y Bosco Ntaganda eran sin duda acreedoras de dicha protección.

EL CAMINO DE MULAS EN COSTA RICA Y PANAMA

El Camino de Mulas, con excepción de las veredas y trillos precolombinos, fue el primero, y por muchos años el único camino para las comunicaciones interiores y exteriores. El camino fue construido ya en 1601 con el objeto de unir Cartago (en la  oriental de la Depresión Tectónica Central) con Tierra Firme (Panamá), pero también el camino contribuyo a unir Nicaragua, Costa Rica y Panamá. Por el se transportaban los productos y materias primas hasta la feria de Portobelo y desde esta las mercaderías por el mismo camino hacia las colonias. El tráfico origino importantes ingresos públicos y con ellos fue posible pagar los gastos militares y administrativos de la provincia. Ejemplos de contratos de venta, hipotecas y opciones de compraventa, incluso por parte de eclesiásticos, son presentados en el trabajo. Sin embargo, la supresión de la feria en 1746, determinó la decadencia económica de Panamá, la reducción del tráfico de mulas a lo largo del camino y la subsecuente disminución y, finalmente, la desaparición de los impuestos, todo lo cual puede ser verificado en las cuencas de Tesoro Real de la provincia de Costa Rica.  ABSTRACT The Mule Trail, with exceptions to the Pre-colombian footpaths, was the first, and for many years the only, interior and international communications route. The trail was constructed in 1601 with the object being to link Cartago (in the Eastern Sub-Basin of the Central Tectonic Depression) with Tierra Firme (Panamá) but also the trail contributed in linking Nicaragua, Costa Rica and Panamá because it permitted. The transportation of products and raw materials to the Portobelo fair and also allowed Spanish merchandise to arrive to the colonies. The traffic originated ingresses and with the money it was possible to pay the Administrative and Military debts of the province. Example of sales contracts, mortgages and buying and selling options, even used by the ecclesiastics, are presented in this essay.  Nevertheless, the suppression of the fair in 1746, determined the economic decadence of Panamá, the reduction of mule traffic over the trail and the subsequent diminish and finally disappearance of the accounting of the Royal Treasury of the Province of Costa Rica.

The condition, development and suggestions of policy of the highway express freight transportation system in China

The highway express freight transportation (HEFT) is a new transportation organization form separated from the common freight transportation with economic development and incessant adjustment of highway transportation structure in China. At present, the phenomenon of inadaptability still exists in the HEFT system of China, from foundation structure like highways, parking lots and stations to transportation equipments and transportation organizing. In order to develop the HEFT system more rationally and effectively, we should start with the structure of the system, conform the resources existing, and consummate the freight transport system. In due course, relevant policies and measures to supervise, lead and support are necessary and important. This paper analyzes the existing problems of HEFT system in our country, based on its characteristics, development situation and adaptability, and presents the policy and measures of promoting and leading the development of the HEFT system.

Long-term outcomes of seriously injured children : a study using the Child Health Questionnaire

Objective: To assess the health-related quality of life (HRQoL) in children 1-2 years after they had sustained an injury. Methods: Parents of all children who were identified by the Queensland Trauma Registry during their admission to either of the two paediatric specialty hospitals in Brisbane, Australia, for the treatment of an injury, were invited to participate in this study. Parents who consented to participation received a copy of the Child Health Questionnaire (CHQ) that required them to provide information regarding their child’s HRQoL following injury. The CHQ scores for the study respondents were compared with those of the Australian norms. This study was approved by the relevant ethics committees. Results: Two hundred and forty-one completed questionnaires were returned. The majority of cases were male (65%) and there was even representation across all age groups. The majority of injuries were considered to be minor (81%) and were predominantly the result of falls and cycling accidents causing mainly fractures and intracranial injury. On the majority of subscales of the CHQ, study participants recorded scores that were statistically significantly below those of the Australian norms. None of the relevant variables collected by the Queensland Trauma Registry were found to predict scores on the CHQ in this study (for those children hospitalized for >24 h). Conclusion: Injured children are worse off than their Australian counterparts in terms of HRQoL even up to 2 years following an injury. Further research needs to be undertaken to identify factors that predict lower HRQoL in order to reduce the burden of injury on children and their families.