More Like this

1. The single robot line coverage problem: Theory, algorithms, and experiments

   https://doi.org/10.1002/net.22171  

   Agarwal, Saurav; Akella, Srinivas (July 2023, Networks)

   Abstract Line coverage is the task of servicing a given set of one‐dimensional features in an environment. It is important for the inspection of linear infrastructure such as road networks, power lines, and oil and gas pipelines. This paper addresses the single robot line coverage problem for aerial and ground robots by modeling it as an optimization problem on a graph. The problem belongs to the broad class of arc routing problems and is closely related to the rural postman problem (RPP) on asymmetric graphs. The paper presents an integer linear programming formulation with proofs of correctness. Using the minimum cost flow problem, we develop approximation algorithms with guarantees on the solution quality. These guarantees also improve the existing results for the asymmetric RPP. The main algorithm partitions the problem into three cases based on the structure of therequired graph, that is, the graph induced by the features that require servicing. We evaluate our algorithms on road networks from the 50 most populous cities in the world, consisting of up to 730 road segments. The algorithms, augmented with improvement heuristics, run within 3 s and generate solutions that are within 10% of the optimum. We experimentally demonstrate our algorithms with commercial UAVs on the UNC Charlotte campus road network. 

   more » « less
2. Approximation Algorithms for the Single Robot Line Coverage Problem

   https://doi.org/10.1007/978-3-030-66723-8_32  

   Agarwal, Saurav; Akella, Srinivas (January 2021, Algorithmic Foundations of Robotics XIV (WAFR 2020))

   LaValle, Steve M.; Lin, Ming; Ojala, Timo; Shell, Dylan; Yu, Jingjin (Ed.)

   The line coverage problem is the task of servicing a given set of one-dimensional features in an environment. Its applications include the inspection of road networks, power lines, and oil and gas lines. The line coverage problem is a generalization of the standard arc routing problems, and is NP-hard in general. We address the single robot line coverage problem where the service and deadhead costs are distinct and asymmetric. We model the problem as an optimization problem that minimizes the total cost of travel on a given graph. We present approximation algorithms to obtain bounded solutions efficiently, using the minimum cost flow problem. We build the main algorithm in stages by considering three simpler subproblems. The subproblems are based on the structure of the required graph, i.e., the graph induced by the features that require servicing. We fi rst present an optimal algorithm for the case of Eulerian graphs with only required edges. Next we consider general graphs, not necessarily Eulerian, with only required edges and present a 2-approximation algorithm. Finally, we consider the general case with both required and non-required edges. The approximation algorithm is dependent on the Asymmetric Traveling Salesperson Problem (ATSP), and is bounded by alpha(C) + 2, where alpha(C) is the approximation factor of the ATSP algorithm with C connected components. Our upper bound is also an improvement over the existing results for the asymmetric rural postman problem. 

   more » « less
3. Summarizing the solution space in tumor phylogeny inference by multiple consensus trees

   https://doi.org/10.1093/bioinformatics/btz312  

   Aguse, Nuraini; Qi, Yuanyuan; El-Kebir, Mohammed (July 2019, Bioinformatics)

   Abstract MotivationCancer phylogenies are key to studying tumorigenesis and have clinical implications. Due to the heterogeneous nature of cancer and limitations in current sequencing technology, current cancer phylogeny inference methods identify a large solution space of plausible phylogenies. To facilitate further downstream analyses, methods that accurately summarize such a set T of cancer phylogenies are imperative. However, current summary methods are limited to a single consensus tree or graph and may miss important topological features that are present in different subsets of candidate trees. ResultsWe introduce the Multiple Consensus Tree (MCT) problem to simultaneously cluster T and infer a consensus tree for each cluster. We show that MCT is NP-hard, and present an exact algorithm based on mixed integer linear programming (MILP). In addition, we introduce a heuristic algorithm that efficiently identifies high-quality consensus trees, recovering all optimal solutions identified by the MILP in simulated data at a fraction of the time. We demonstrate the applicability of our methods on both simulated and real data, showing that our approach selects the number of clusters depending on the complexity of the solution space T. Availability and implementationhttps://github.com/elkebir-group/MCT. Supplementary informationSupplementary data are available at Bioinformatics online. 

   more » « less
4. A new 3/2-approximation algorithm for the b-edge cover problem

   https://doi.org/10.1137/1.9781611974690.ch6  

   Khan, Arif H.; Pothen, Alex (January 2016, Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing)

   We describe a 3/2-approximation algorithm, \lse, for computing a b-edgecover of minimum weight in a graph with weights on the edges. The b-edgecover problem is a generalization of the better-known Edge Cover problem in graphs, where the objective is to choose a subset C of edges in the graph such that at least a specified number b(v) of edges in C are incident on each vertex v. In the weighted b-edgecover problem, we minimize the sum of the weights of the edges in C. We prove that the Locally Subdominant edge (LSE) algorithm computes the same b-edge cover as the one obtained by the Greedy algorithm for the problem. However, the Greedy algorithm requires edges to be sorted by their effective weights, and these weights need to be updated after each iteration. These requirements make the Greedy algorithm sequential and impractical for massive graphs. The LSE algorithm avoids the sorting step, and is amenable for parallelization. We implement the algorithm on a serial machine and compare its performance against a collection of approximation algorithms for the b-edge cover problem. Our results show that the algorithm is 3 to 5 times faster than the Greedy algorithm on a serial processor. The approximate edge covers obtained by the LSE algorithm have weights greater by at most 17% of the optimal weight for problems where we could compute the latter. We also investigate the relationship between the b-edge cover and the b-matching problems, show that the latter has a faster implementation since edge weights are static in this algorithm, and obtain a heuristic solution for the former from the latter. 

   more » « less
5. A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges

   https://doi.org/10.7155/jgaa.00609  

   Bader, David A.; Burkhardt, Paul (January 2022, Journal of Graph Algorithms and Applications)

   Given an undirected, weighted graph, the minimum spanning tree (MST)is a tree that connects all of the vertices of the graph with minimum sum of edge weights. In real world applications, network designers often seek to quickly find a replacement edge for each edge in the MST. For example, when a traffic accident closes a road in a transportation network, or a line goes down in a communication network, the replacement edge may reconnect the MST at lowest cost. In the paper, we consider the case of finding the lowest cost replacement edge for each edge of the MST. A previous algorithm by Tarjan takes O{m lpha(m, n)} time and space, where $lpha(m, n)$ is the inverse Ackermann’s function. Given the MST and sorted non-tree edges, our algorithm is the first practical algorithm that runs in O(m+n) time and O(m+n) space to find all replacement edges. Additionally, since the most vital edge is the tree edge whose removal causes the highest cost, our algorithm finds it in linear time. 

   more » « less