More Like this

1. 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
2. Line Coverage with Multiple Robots

   https://doi.org/10.1109/ICRA40945.2020.9197292  

   Agarwal, Saurav; Akella, Srinivas (June 2020, IEEE International Conference on Robotics and Automation)

   The line coverage problem is the coverage of linear environment features (e.g., road networks, power lines), modeled as 1D segments, by one or more robots while respecting resource constraints (e.g., battery capacity, flight time) for each of the robots. The robots incur direction dependent costs and resource demands as they traverse the edges. We treat the line coverage problem as an optimization problem, with the total cost of the tours as the objective, by formulating it as a mixed integer linear program (MILP). The line coverage problem is NP-hard and hence we develop a heuristic algorithm, Merge- Embed-Merge (MEM). We compare it against the optimal MILP approach and a baseline heuristic algorithm, Extended Path Scanning. We show the MEM algorithm is fast and suitable for real-time applications. To tackle large-scale problems, our approach performs graph simplification and graph partitioning, followed by robot tour generation for each of the partitioned subgraphs. We demonstrate our approach on a large graph with 4,658 edges and 4,504 vertices that represents an urban region of about 16 sq. km. We compare the performance of the algorithms on several small road networks and experimentally demonstrate the approach using UAVs on the UNC Charlotte campus road network. 

   more » « less
3. New Spectral Algorithms for Refuting Smoothed k-SAT

   https://doi.org/10.1145/3635117  

   Guruswami, Venkatesan; Kothari, Pravesh K; Manohar, Peter (March 2025, Communications of the ACM)

   Despite being a quintessential example of a hard problem, the quest for finding fast algorithms for deciding satisfiability of propositional formulas has occupied computer scientists both in theory and in practice. In this article, we survey recent progress on designing algorithms with strong refutation guarantees forsmoothedinstances of the $k$-SAT problem. Smoothed instances are formed by slight random perturbations of arbitrary instances, and their study is a way to bridge the gap between worst-case and average-case models of problem instances. Our methods yield new algorithms for smoothed $k$-SAT instances with guarantees that match those for the significantly simpler and well-studied model ofrandomformulas. Additionally, they have led to a novel and unexpected line of attack on some longstanding extremal combinatorial problems in graph theory and coding theory. As an example, we will discuss the resolution of a 2008 conjecture of Feige on the existence of short cycles in hypergraphs. 

   more » « less
4. Conformal Prediction with Learned Features

   Kiyani, Shayan; Pappas, George; Hassani, Hamed (July 2024, ICML)

   In this paper, we focus on the problem of conformal prediction with conditional guarantees. Prior work has shown that it is impossible to construct nontrivial prediction sets with full conditional coverage guarantees. A wealth of research has considered relaxations of full conditional guarantees, relying on some predefined uncertainty structures. Departing from this line of thinking, we propose Partition Learning Conformal Prediction (PLCP), a framework to improve conditional validity of prediction sets through learning uncertainty-guided features from the calibration data. We implement PLCP efficiently with alternating gradient descent, utilizing off-the-shelf machine learning models. We further analyze PLCP theoretically and provide conditional guarantees for infinite and finite sample sizes. Finally, our experimental results over four real-world and synthetic datasets show the superior performance of PLCP compared to state-of-the-art methods in terms of coverage and length in both classification and regression scenarios. 

   more » « less
5. Current Flow Group Closeness Centrality for Complex Networks?

   https://doi.org/10.1145/3308558.3313490  

   Li, Huan; Peng, Richard; Shan, Liren; Yi, Yuhao; Zhang, Zhongzhi (June 2019, The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019)

   Current flow closeness centrality (CFCC) has a better discriminating ability than the ordinary closeness centrality based on shortest paths. In this paper, we extend this notion to a group of vertices in a weighted graph, and then study the problem of finding a subset S of k vertices to maximize its CFCC C(S), both theoretically and experimentally. We show that the problem is NP-hard, but propose two greedy algorithms for minimizing the reciprocal of C(S) with provable guarantees using the monotoncity and supermodularity. The first is a deterministic algorithm with an approximation factor (1−kk−1⋅1e) and cubic running time; while the second is a randomized algorithm with a (1−kk−1⋅1e−ϵ)-approximation and nearly-linear running time for any ϵ>0. Extensive experiments on model and real networks demonstrate that our algorithms are effective and efficient, with the second algorithm being scalable to massive networks with more than a million vertices. 

   more » « less