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.

Financial Statement Analysis for Enterprise Network Design

Part 8: Business Strategies Alignment

Hybrid ground-aerial mesh networks for IoT monitoring applications: network design and software platform development

The Internet of Things (IoT) has grown rapidly in recent years, leading to an increased need for efficient and secure communication between connected devices. Wireless Sensor Networks (WSNs) are composed of small, low-power devices that are capable of sensing and exchanging data, and are often used in IoT applications. In addition, Mesh WSNs involve intermediate nodes forwarding data to ensure more robust communication. The integration of Unmanned Aerial Vehicles (UAVs) in Mesh WSNs has emerged as a promising solution for increasing the effectiveness of data collection, as UAVs can act as mobile relays, providing extended communication range and reducing energy consumption. However, the integration of UAVs and Mesh WSNs still poses new challenges, such as the design of efficient control and communication strategies. This thesis explores the networking capabilities of WSNs and investigates how the integration of UAVs can enhance their performance. The research focuses on three main objectives: (1) Ground Wireless Mesh Sensor Networks, (2) Aerial Wireless Mesh Sensor Networks, and (3) Ground/Aerial WMSN integration. For the first objective, we investigate the use of the Bluetooth Mesh standard for IoT monitoring in different environments. The second objective focuses on deploying aerial nodes to maximize data collection effectiveness and QoS of UAV-to-UAV links while maintaining the aerial mesh connectivity. The third objective investigates hybrid WMSN scenarios with air-to-ground communication links. One of the main contribution of the thesis consists in the design and implementation of a software framework called "Uhura", which enables the creation of Hybrid Wireless Mesh Sensor Networks and abstracts and handles multiple M2M communication stacks on both ground and aerial links. The operations of Uhura have been validated through simulations and small-scale testbeds involving ground and aerial devices.

Towards an Academic Social Network for Bologna Process

The Bologna Process aimed to build a European Higher Education Area promoting student's mobility. The adoption of Bologna Declaration directives requires a self management distributed approach to deal with student's mobility, allowing frequent updates in institutions rules or legislation. This paper suggests a computational system architecture, which follows a social network design. A set of structured annotations is proposed in order to organize the user's information. For instance, when the user is a student its annotations are organized into an academic record. The academic record data is used to discover interests, namely mobility interests, among students that belongs the academic network. These ideas have been applied into a demonstrator that includes a mobility simulator to compare and show the student's academic evolution.

Availability analysis of GMPLS connections based on physical network topology

This paper presents a study of connection availability in GMPLS over optical transport networks (OTN) taking into account different network topologies. Two basic path protection schemes are considered and compared with the no protection case. The selected topologies are heterogeneous in geographic coverage, network diameter, link lengths, and average node degree. Connection availability is also computed considering the reliability data of physical components and a well-known network availability model. Results show several correspondences between suitable path protection algorithms and several network topology characteristics

INFO6003: Campus Network Security Perspectives

These slides cover aspects of network design and technology relevant to a campus network deployment such as that at the University of Southampton.

A Productivity-Based Approach to LAN Topology Design

Over the useful life of a LAN, network downtimes will have a negative impact on organizational productivity not included in current Network Topological Design (NTD) problems. We propose a new approach to LAN topological design that includes the impact of these productivity losses into the network design, minimizing not only the CAPEX but also the expected cost of unproductiveness attributable to network downtimes over a certain period of network operation.

A DOE based approach for the design of RBF artificial neural networks applied to prediction of surface roughness in AISI 52100 hardened Steel turning

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Identification of lubricant contamination by biodiesel using vibration analysis and neural network

Purpose - The purpose of this paper is to provide information on lubricant contamination by biodiesel using vibration and neural network.Design/methodology/approach - The possible contamination of lubricants is verified by analyzing the vibration and neural network of a bench test under determinated conditions.Findings - Results have shown that classical signal analysis methods could not reveal any correlation between the signal and the presence of contamination, or contamination grade. on other hand, the use of probabilistic neural network (PNN) was very successful in the identification and classification of contamination and its grade.Research limitations/implications - This study was done for some specific kinds of biodiesel. Other types of biodiesel could be analyzed.Practical implications Contamination information is presented in the vibration signal, even if it is not evident by classical vibration analysis. In addition, the use of PNN gives a relatively simple and easy-to-use detection tool with good confidence. The training process is fast, and allows implementation of an adaptive training algorithm.Originality/value - This research could be extended to an internal combustion engine in order to verify a possible contamination by biodiesel.

Optimization of Radial Basis Function neural network employed for prediction of surface roughness in hard turning process using Taguchi's orthogonal arrays

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Design of in-building wireless networks deployments using evolutionary algorithms

In this article, a novel approach to deal with the design of in-building wireless networks deployments is proposed. This approach known as MOQZEA (Multiobjective Quality Zone Based Evolutionary Algorithm) is a hybr id evolutionary algorithm adapted to use a novel fitness function, based on the definition of quality zones for the different objective functions considered. This approach is conceived to solve wireless network design problems without previous information of the required number of transmitters, considering simultaneously a high number of objective functions and optimizing multiple configuration parameters of the transmitters.

Ypres rally network

Along of this document the reader could find a suitable network design and solution for the Rally Championship of Ypres meeting all the requirements set by the organization of the rally. These requirements have brought many problems in accordance with the network standards, because the area where the boxes are located is pretty large nevertheless technologies to solve those problems are detailed in the project. It has been included different designs in the project, each one of them based on distinct characteristic as they could be efficient, performance… , and the most important, since the organization of the rally is non-profit , the budget. Nevertheless we didn’t dismiss the use of long-lasting devices, as CISCO devices, despite their price. Furthermore a configuration of routing/switching devices has been explained for those who will be commanded to implement this solution. This solution is design to supply internet access as well as video streaming to all boxes for what teams can follow the championship in live time. The maximum connection of internet service provider (ISP) is 160Mbps, this bandwidth has to be distributed for the boxes dynamically. Finally to ensure the network works out it has to be monitored, this is reachable by using network analysis tools which in this project Wireshark has been chosen. RESUMEN. A lo largo de este documento, el lector encontrara un posible diseño y una posible solución para la red local del circuito de Rally celebrado en Ypres, cumpliendo con todos los requisitos y especificaciones establecidos por la organización. Estos requisitos han causado problemas de conformidad con los estándares de la red, debido a que la zona donde se encuentran los Boxes de los equipos es bastante larga, sin embargo las tecnologías para resolver esos problemas se detallan en este proyecto. Se han incluido diferentes diseños, cada uno de ellos centrado en aspectos diferentes así como la eficacia, el rendimiento, el presupuesto, etc... Esta solución está diseñada para suministrar acceso a Internet, así como la transmisión dinámica de video a todos los equipos para que puedan seguir la competición en tiempo real. Finalmente para controlar y asegurar que la red funciona, será monitorizada mediante herramientas de análisis de redes (Wireshark).

Independent modulation of engagement and connectivity of the facial network during affect processing by CACNA1C and ANK3 risk genes for bipolar disorder

IMPORTANCE Genome-wide association studies (GWASs) indicate that single-nucleotide polymorphisms in the CACNA1C and ANK3 genes increase the risk for bipolar disorder (BD). The genes influence neuronal firing by modulating calcium and sodium channel functions, respectively. Both genes modulate ?-aminobutyric acid-transmitting interneuron function and can thus affect brain regional activation and interregional connectivity. OBJECTIVE To determine whether the genetic risk for BD associated with 2 GWAS-supported risk single-nucleotide polymorphisms at CACNA1C rs1006737 and ANK3 rs10994336 is mediated through changes in regional activation and interregional connectivity of the facial affect-processing network. DESIGN, SETTING, AND PARTICIPANTS Cross-sectional functional magnetic resonance imaging study at a research institute of 41 euthymic patients with BD and 46 healthy participants, all of British white descent. MAIN OUTCOMES AND MEASURES Blood oxygen level-dependent signal and effective connectivity measures during the facial affect-processing task. RESULTS In healthy carriers, both genetic risk variants were independently associated with increased regional engagement throughout the facial affect-processing network and increased effective connectivity between the visual and ventral prefrontal cortical regions. In contrast, BD carriers of either genetic risk variant exhibited pronounced reduction in ventral prefrontal cortical activation and visual-prefrontal effective connectivity. CONCLUSIONS AND RELEVANCE Our data demonstrate that the effect of CACNA1C rs1006737 and ANK3 rs10994336 (or genetic variants in linkage disequilibrium) on the brain converges on the neural circuitry involved in affect processing and provides a mechanism linking BD to genome-wide genetic risk variants.

Reconfiguration of supply chain network:an ISM-based roadmap to performance

Purpose: Short product life cycle and/or mass customization necessitate reconfiguration of operational enablers of supply chain (SC) from time to time in order to harness high levels of performance. The purpose of this paper is to identify the key operational enablers under stochastic environment on which practitioner should focus while reconfiguring a SC network. Design/methodology/approach: The paper used interpretive structural modeling (ISM) approach that presents a hierarchy-based model and the mutual relationships among the enablers. The contextual relationship needed for developing structural self-interaction matrix (SSIM) among various enablers is realized by conducting experiments through simulation of a hypothetical SC network. Findings: The research identifies various operational enablers having a high driving power towards assumed performance measures. In this regard, these enablers require maximum attention and of strategic importance while reconfiguring SC. Practical implications: ISM provides a useful tool to the SC managers to strategically adopt and focus on the key enablers which have comparatively greater potential in enhancing the SC performance under given operational settings. Originality/value: The present research realizes the importance of SC flexibility under the premise of reconfiguration of the operational units in order to harness high value of SC performance. Given the resulting digraph through ISM, the decision maker can focus the key enablers for effective reconfiguration. The study is one of the first efforts that develop contextual relations among operational enablers for SSIM matrix through integration of discrete event simulation to ISM. © Emerald Group Publishing Limited.