More Like this

1. Finding Your Way: Shortest Paths on Networks

   https://doi.org/10.3389/frym.2021.631045  

   Rexin, Teresa; Porter, Mason A. (December 2021, Frontiers for Young Minds)

   Traveling to different destinations is a major part of our lives. We visit a variety of locations both during our daily lives and when we are on vacation. How can we find the best way to navigate from one place to another? Perhaps we can test all of the different ways of traveling between two places, but another method is to use mathematics and computation to find a shortest path between them. In this article, we discuss how to construct shortest paths and introduce Dijkstra’s algorithm to minimize the total cost of a path, where the cost may be the travel distance, the travel time, or some other quantity. We also discuss how to use shortest paths in the real world to save time and increase traveling efficiency. 

   more » « less
2. Perspective: Wearable Internet of Medical Things for Remote Tracking of Symptoms, Prediction of Health Anomalies, Implementation of Preventative Measures, and Control of Virus Spread During the Era of COVID-19

   https://doi.org/10.3389/frobt.2021.610653  

   Mehrdad, Sarmad; Wang, Yao; Atashzar, S. Farokh (April 2021, Frontiers in Robotics and AI)

   null (Ed.)

   The COVID-19 pandemic has highly impacted the communities globally by reprioritizing the means through which various societal sectors operate. Among these sectors, healthcare providers and medical workers have been impacted prominently due to the massive increase in demand for medical services under unprecedented circumstances. Hence, any tool that can help the compliance with social guidelines for COVID-19 spread prevention will have a positive impact on managing and controlling the virus outbreak and reducing the excessive burden on the healthcare system. This perspective article disseminates the perspectives of the authors regarding the use of novel biosensors and intelligent algorithms embodied in wearable IoMT frameworks for tackling this issue. We discuss how with the use of smart IoMT wearables certain biomarkers can be tracked for detection of COVID-19 in exposed individuals. We enumerate several machine learning algorithms which can be used to process a wide range of collected biomarkers for detecting (a) multiple symptoms of SARS-CoV-2 infection and (b) the dynamical likelihood of contracting the virus through interpersonal interaction. Eventually, we enunciate how a systematic use of smart wearable IoMT devices in various social sectors can intelligently help controlling the spread of COVID-19 in communities as they enter the reopening phase. We explain how this framework can benefit individuals and their medical correspondents by introducing Systems for Symptom Decoding (SSD), and how the use of this technology can be generalized on a societal level for the control of spread by introducing Systems for Spread Tracing (SST). 

   more » « less
3. A Constrained Shortest Path Scheme for Virtual Network Service Management

   https://doi.org/10.1109/TNSM.2018.2865204  

   Chemodanov, Dmitrii; Esposito, Flavio; Calyam, Prasad; Sukhov, Andrei (August 2018, IEEE Transactions on Network and Service Management)

   Virtual network services that span multiple data centers are important to support emerging data-intensive applications in fields such as bioinformatics and retail analytics. Successful virtual network service composition and maintenance requires flexible and scalable ‘constrained shortest path management’ both in the management plane for virtual network embedding (VNE) or network function virtualization service chaining (NFV-SC), as well as in the data plane for traffic engineering (TE). In this paper, we show analytically and empirically that leveraging constrained shortest paths within recent VNE, NFV-SC and TE algorithms can lead to network utilization gains (of up to 50%) and higher energy efficiency. The management of complex VNE, NFV-SC and TE algorithms can be, however, intractable for large scale substrate networks due to the NP-hardness of the constrained shortest path problem. To address such scalability challenges, we propose a novel, exact constrained shortest path algorithm viz.‘, Neighborhoods Method’ (NM). Our NM uses novel search space reduction techniques and has a theoretical quadratic speed-up making it practically faster (by an order of magnitude) than recent branch-and-bound exhaustive search solutions. Finally, we detail our NM-based SDN controller implementation in a real-world testbed to further validate practical NM benefits for virtual network services. 

   more » « less
4. Approximation Algorithms for 𝓁_p-Shortest Path and 𝓁_p-Group Steiner Tree

   https://doi.org/10.4230/LIPIcs.ICALP.2024.111  

   Makarychev, Yury; Ovsiankin, Max; Tani, Erasmo (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola (Ed.)

   We present polylogarithmic approximation algorithms for variants of the Shortest Path, Group Steiner Tree, and Group ATSP problems with vector costs. In these problems, each edge e has a vector cost c_e ∈ ℝ_{≥0}^𝓁;. For a feasible solution - a path, subtree, or tour (respectively) - we find the total vector cost of all the edges in the solution and then compute the 𝓁_p-norm of the obtained cost vector (we assume that p ≥ 1 is an integer). Our algorithms for series-parallel graphs run in polynomial time and those for arbitrary graphs run in quasi-polynomial time. To obtain our results, we introduce and use new flow-based Sum-of-Squares relaxations. We also obtain a number of hardness results. 

   more » « less
5. Map-matching using shortest paths

   https://doi.org/10.1145/3191801.3191812  

   Chambers, Erin; Fasy, Brittany Terese; Wang, Yusu; Wenk, Carola (January 2018, IWISC)

   We consider several variants of the map-matching problem, which seeks to find a path Q in graph G that has the smallest distance to a given trajectory P (which is likely not to be exactly on the graph). In a typical application setting, P models a noisy GPS trajectory from a person traveling on a road network, and the desired path Q should ideally correspond to the actual path in G that the person has traveled. Existing map-matching algorithms in the literature consider all possible paths in G as potential candidates for Q. We find solutions to the map-matching problem under different settings. In particular, we restrict the set of paths to shortest paths, or concatenations of shortest paths, in G. As a distance measure, we use the Fréchet distance, which is a suitable distance measure for curves since it takes the continuity of the curves into account. 

   more » « less