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.

Probabilistic approach of water residence time and connectivity using Markov Chains with application to tidal embayments

Markov Chain analysis was recently proposed to assess the time scales and preferential pathways into biological or physical networks by computing residence time, first passage time, rates of transfer between nodes and number of passages in a node. We propose to adapt an algorithm already published for simple systems to physical systems described with a high resolution hydrodynamic model. The method is applied to bays and estuaries on the Eastern Coast of Canada for their interest in shellfish aquaculture. Current velocities have been computed by using a 2 dimensional grid of elements and circulation patterns were summarized by averaging Eulerian flows between adjacent elements. Flows and volumes allow computing probabilities of transition between elements and to assess the average time needed by virtual particles to move from one element to another, the rate of transfer between two elements, and the average residence time of each system. We also combined transfer rates and times to assess the main pathways of virtual particles released in farmed areas and the potential influence of farmed areas on other areas. We suggest that Markov chain is complementary to other sets of ecological indicators proposed to analyse the interactions between farmed areas - e.g. depletion index, carrying capacity assessment. Markov Chain has several advantages with respect to the estimation of connectivity between pair of sites. It makes possible to estimate transfer rates and times at once in a very quick and efficient way, without the need to perform long term simulations of particle or tracer concentration.

On the rotation of co-orbital bodies in eccentric orbits

We investigate the resonant rotation of co-orbital bodies in eccentric and planar orbits. We develop a simple analytical model to study the impact of the eccentricity and orbital perturbations on the spin dynamics. This model is relevant in the entire domain of horseshoe and tadpole orbit, for moderate eccentricities. We show that there are three different families of spin-orbit resonances, one depending on the eccentricity, one depending on the orbital libration frequency, and another depending on the pericenter's dynamics. We can estimate the width and the location of the different resonant islands in the phase space, predicting which are the more likely to capture the spin of the rotating body. In some regions of the phase space the resonant islands may overlap, giving rise to chaotic rotation.

Is the activity level of HD 80606 influenced by its eccentric planet?

Aims: Several studies suggest that the activity level of a planet-host star can be influenced by the presence of a close-by orbiting planet. Moreover, the interaction mechanisms that have been proposed, magnetic interaction and tidal interaction, exhibit a very different dependence on the orbital separation between the star and the planet. A detection of activity enhancement and characterization of its dependence on planetary orbital distance can, in principle, allow us to characterize the physical mechanism behind the activity enhancement. Methods: We used the HARPS-N spectrograph to measure the stellar activity level of HD 80606 during the planetary periastron passage and compared the activity measured to that close to apastron. Being characterized by an eccentricity of 0.93 and an orbital period of 111 days, the system's extreme variation in orbital separation makes it a perfect target to test our hypothesis. Results: We find no evidence for a variation in the activity level of the star as a function of planetary orbital distance, as measured by all activity indicators employed: log(R'HK), Hα, NaI, and HeI. None of the models employed, whether magnetic interaction or tidal interaction, provides a good description of the data. The photometry revealed no variation either, but it was strongly affected by poor weather conditions. Conclusions: We find no evidence for star-planet interaction in HD 80606 at the moment of the periastron passage of its very eccentric planet. The straightforward explanation for the non-detection is the absence of interaction as a result of a low magnetic field strength on either the planet or the star and of the low level of tidal interaction between the two. However, we cannot exclude two scenarios: i) the interaction can be instantaneous and of magnetic origin, being concentrated on the substellar point and its surrounding area; and ii) the interaction can lead to a delayed activity enhancement. In either scenario, a star-planet interaction would not be detectable with the dataset described in this paper.

Content and Connectivity in the Age of Digital Libraries

"Behind the world of virtual university is more than a method or system of work, you need to own, develop and master a connectivity structure of both technological and content development in multimedia digital text and then implement teaching methods line. "

Using landscape metrics to predict hydrologic connectivity patterns between forested wetlands and streams in a coastal plain watershed

Geographically isolated wetlands, those entirely surrounded by uplands, provide numerous ecological functions, some of which are dependent on the degree to which they are hydrologically connected to nearby waters. There is a growing need for field-validated, landscape-scale approaches for classifying wetlands based on their expected degree of connectivity with stream networks. During the 2015 water year, flow duration was recorded in non-perennial streams (n = 23) connecting forested wetlands and nearby perennial streams on the Delmarva Peninsula (Maryland, USA). Field and GIS-derived landscape metrics (indicators of catchment, wetland, non-perennial stream, and soil characteristics) were assessed as predictors of wetland-stream connectivity (duration, seasonal onset and offset dates). Connection duration was most strongly correlated with non-perennial stream geomorphology and wetland characteristics. A final GIS-based stepwise regression model (adj-R2 = 0.74, p < 0.0001) described wetland-stream connection duration as a function of catchment area, wetland area and number, and soil available water storage.

A divide-and-conquer bound for aggregate's quality and algebraic connectivity

info:eu-repo/semantics/submittedForPublication

Assessing land–ocean connectivity via submarine groundwater discharge (SGD) in the Ria Formosa Lagoon (Portugal): combining radon measurements and stable isotope hydrology

Natural radioactive tracer-based assessments of basin-scale submarine groundwater discharge (SGD) are well developed. However, SGD takes place in different modes and the flow and discharge mechanisms involved occur over a wide range of spatial and temporal scales. Quantifying SGD while discriminating its source functions therefore remains a major challenge. However, correctly identifying both the fluid source and composition is critical. When multiple sources of the tracer of interest are present, failure to adequately discriminate between them leads to inaccurate attribution and the resulting uncertainties will affect the reliability of SGD solute loading estimates. This lack of reliability then extends to the closure of local biogeochemical budgets, confusing measures aiming to mitigate pollution. Here, we report a multi-tracer study to identify the sources of SGD, distinguish its component parts and elucidate the mechanisms of their dispersion throughout the Ria Formosa – a seasonally hypersaline lagoon in Portugal. We combine radon budgets that determine the total SGD (meteoric + recirculated seawater) in the system with stable isotopes in water (δ2H, δ18O), to specifically identify SGD source functions and characterize active hydrological pathways in the catchment. Using this approach, SGD in the Ria Formosa could be separated into two modes, a net meteoric water input and another involving no net water transfer, i.e., originating in lagoon water re-circulated through permeable sediments. The former SGD mode is present occasionally on a multi-annual timescale, while the latter is a dominant feature of the system. In the absence of meteoric SGD inputs, seawater recirculation through beach sediments occurs at a rate of  ∼  1.4  ×  106 m3 day−1. This implies that the entire tidal-averaged volume of the lagoon is filtered through local sandy sediments within 100 days ( ∼  3.5 times a year), driving an estimated nitrogen (N) load of  ∼  350 Ton N yr−1 into the system as NO3−. Land-borne SGD could add a further  ∼  61 Ton N yr−1 to the lagoon. The former source is autochthonous, continuous and responsible for a large fraction (59 %) of the estimated total N inputs into the system via non-point sources, while the latter is an occasional allochthonous source capable of driving new production in the system.

Genetic diversity and connectivity remain high in Holothuria polii (Delle Chiaje 1823) across a coastal lagoon-open sea environmental gradient

Coastal lagoons represent habitats with widely heterogeneous environmental conditions, particularly as regards salinity and temperature,which fluctuate in both space and time. These characteristics suggest that physical and ecological factors could contribute to the genetic divergence among populations occurring in coastal lagoon and opencoast environments. This study investigates the genetic structure of Holothuria polii at a micro-geographic scale across theMar Menor coastal lagoon and nearbymarine areas, estimating the mitochondrial DNA variation in two gene fragments, cytochrome oxidase I (COI) and 16S rRNA (16S). Dataset of mitochondrial sequences was also used to test the influence of environmental differences between coastal lagoon andmarine waters on population genetic structure. All sampled locations exhibited high levels of haplotype diversity and low values of nucleotide diversity. Both genes showed contrasting signals of genetic differentiation (non-significant differences using COI and slight differences using 16S, which could due to different mutation rates or to differential number of exclusive haplotypes. We detected an excess of recent mutations and exclusive haplotypes, which can be generated as a result of population growth. However, selective processes can be also acting on the gene markers used; highly significant generalized additive models have been obtained considering genetic data from16S gene and independent variables such as temperature and salinity.

Genetic differentiation among Parastichopus regalis populations in the Western Mediterranean Sea: potential effects from its fishery and current connectivity

Parastichopus regalis (Cuvier, 1817) is the most expensive seafood product on the Catalonian market (NE Spain), with prices at approximately 130 €/Kg (fresh weight). Despite its ecological and economic importance, biological and genetic information on this sea cucumber species is scarce. Here, we provide both the first insight on the genetic structure of P. regalis using sequences of cytochrome oxidase I (COI) and 16S genes and a morphological description of its population. Individual sea cucumbers were collected in six locations along the Spanish Mediterranean coast, including an area under fishery pressure (Catalonia). We found high haplotype diversity and low nucleotide diversity for both genes, with higher levels of genetic diversity observed in the COI gene. The population pairwise fixation index (FST), AMOVA and correspondence analysis (CA) based on the COI gene revealed significant genetic differentiation among some locations. However, further analysis using nuclear markers (e.g., microsatellites) is necessary to corroborate these results. Moreover, the genetic and morphological data may indicate fishery effects on the Catalonian population with a decrease in the size and weight averages and lower genetic diversity compared with locations that lack fishery pressure. For the appropriate management of this species, we suggest the following: 1) accurately assessing the stock status along the Spanish coasts; 2) studying the reproductive cycle of this target species and the establishment of a closed fishery season according to the reproductive cycle; and 3) establishing protected areas (i.e., not take zones) to conserve healthy populations and favour recruitment in the nearby areas.

Connectivity patterns inferred from the genetic structure of white seabream (Diplodus sargus L.)

Themarine environment seems, at first sight, to be a homogeneousmediumlacking barriers to species dispersal. Nevertheless, populations of marine species show varying levels of gene flow and population differentiation, so barriers to gene flow can often be detected. Weaimto elucidate the role of oceanographical factors ingenerating connectivity among populations shaping the phylogeographical patterns in the marine realm, which is not only a topic of considerable interest for understanding the evolution ofmarine biodiversity but also formanagement and conservation of marine life. For this proposal,we investigate the genetic structure and connectivity between continental and insular populations ofwhite seabreamin North East Atlantic (NEA) and Mediterranean Sea (MS) aswell as the influence of historical and contemporary factors in this scenario using mitochondrial (cytochrome b) and nuclear (a set of 9 microsatellite) molecular markers. Azores population appeared genetically differentiated in a single cluster using Structure analysis. This result was corroborated by Principal Component Analysis (PCA) and Monmonier algorithm which suggested a boundary to gene flow, isolating this locality. Azorean population also shows the highest significant values of FST and genetic distances for both molecular markers (microsatellites and mtDNA). We suggest that the breakdown of effective genetic exchange between Azores and the others' samples could be explained simultaneously by hydrographic (deep water) and hydrodynamic (isolating current regimes) factors acting as barriers to the free dispersal of white seabream(adults and larvae) and by historical factors which could be favoured for the survival of Azorean white seabream population at the last glaciation. Mediterranean islands show similar genetic diversity to the neighbouring continental samples and nonsignificant genetic differences. Proximity to continental coasts and the current system could promote an optimal larval dispersion among Mediterranean islands (Mallorca and Castellamare) and coasts with high gene flow.

Equivalent norms in polynomial spaces and applications.

In this paper, equivalence constants between various polynomial norms are calculated. As an application, we also obtain sharp values of the Hardy Littlewood constants for 2-homogeneous polynomials on l(p)(2) spaces, 2 < p <= infinity. We also provide lower estimates for the Hardy-Littlewood constants for polynomials of higher degrees.

E-polynomial of SL(2,C)-character varieties of complex curves of genus 3.

We compute the E-polynomials of the moduli spaces of representations of the fundamental group of a complex curve of genus g = 3 into SL(2, C), and also of the moduli space of twisted representations. The case of genus g = 1, 2 has already been done in [12]. We follow the geometric technique introduced in [12], based on stratifying the space of representations, and on the analysis of the behaviour of the E-polynomial under fibrations.

High interannual variability in connectivity and genetic pool of a temperate clingfish matches oceanographic transport predictions

Adults of most marine benthic and demersal fish are site-attached, with the dispersal of their larval stages ensuring connectivity among populations. In this study we aimed to infer spatial and temporal variation in population connectivity and dispersal of a marine fish species, using genetic tools and comparing these with oceanographic transport. We focused on an intertidal rocky reef fish species, the shore clingfish Lepadogaster lepadogaster, along the southwest Iberian Peninsula, in 2011 and 2012. We predicted high levels of self-recruitment and distinct populations, due to short pelagic larval duration and because all its developmental stages have previously been found near adult habitats. Genetic analyses based on microsatellites countered our prediction and a biophysical dispersal model showed that oceanographic transport was a good explanation for the patterns observed. Adult sub-populations separated by up to 300 km of coastline displayed no genetic differentiation, revealing a single connected population with larvae potentially dispersing long distances over hundreds of km. Despite this, parentage analysis performed on recruits from one focal site within the Marine Park of Arrábida (Portugal), revealed self-recruitment levels of 2.5% and 7.7% in 2011 and 2012, respectively, suggesting that both long- and short-distance dispersal play an important role in the replenishment of these populations. Population differentiation and patterns of dispersal, which were highly variable between years, could be linked to the variability inherent in local oceanographic processes. Overall, our measures of connectivity based on genetic and oceanographic data highlight the relevance of long-distance dispersal in determining the degree of connectivity, even in species with short pelagic larval durations.

Structural brain connectivity and cognitive ability differences: A multivariate distance matrix regression analysis

Neuroimaging research involves analyses of huge amounts of biological data that might or might not be related with cognition. This relationship is usually approached using univariate methods, and, therefore, correction methods are mandatory for reducing false positives. Nevertheless, the probability of false negatives is also increased. Multivariate frameworks have been proposed for helping to alleviate this balance. Here we apply multivariate distance matrix regression for the simultaneous analysis of biological and cognitive data, namely, structural connections among 82 brain regions and several latent factors estimating cognitive performance. We tested whether cognitive differences predict distances among individuals regarding their connectivity pattern. Beginning with 3,321 connections among regions, the 36 edges better predicted by the individuals' cognitive scores were selected. Cognitive scores were related to connectivity distances in both the full (3,321) and reduced (36) connectivity patterns. The selected edges connect regions distributed across the entire brain and the network defined by these edges supports high-order cognitive processes such as (a) (fluid) executive control, (b) (crystallized) recognition, learning, and language processing, and (c) visuospatial processing. This multivariate study suggests that one widespread, but limited number, of regions in the human brain, supports high-level cognitive ability differences. Hum Brain Mapp, 2016. © 2016 Wiley Periodicals, Inc.