More Like this

1. Identifying 1-rectifiable measures in Carnot groups

   https://doi.org/10.1515/agms-2023-0102  

   Badger, Matthew; Li, Sean; Zimmerman, Scott (November 2023, Analysis and Geometry in Metric Spaces)

   We continue to develop a program in geometric measure theory that seeks to identify how measures in a space interact with canonical families of sets in the space. In particular, extending a theorem of the first author and R. Schul in Euclidean space, for an arbitrary locally finite Borel measure in an arbitrary Carnot group, we develop tests that identify the part of the measure that is carried by rectifiable curves and the part of the measure that is singular to rectifiable curves. Our main result is entwined with an extension of the Analyst's Traveling Salesman Theorem, which characterizes subsets of rectifiable curves in R^2 (P. Jones, 1990), in R^n (K. Okikolu, 1992), or in an arbitrary Carnot group (the second author) in terms of local geometric least squares data called Jones' beta numbers. In a secondary result, we implement the Garnett-Killip-Schul construction of a doubling measure in R^n that charges a rectifiable curve in an arbitrary complete, doubling, locally quasiconvex metric space. 

   more » « less
2. Arguing Correctness of ASP Programs with Aggregates

   https://doi.org/10.1007/978-3-031-15707-3_15  

   Fandinno, J.; Hansen, Z.; Lierler, Y (August 2022, Arguing Correctness of ASP Programs with Aggregates)

   This paper studies the problem of arguing program correctness for logic programs with aggregates in the context of Answer Set Programming. Cabalar, Fandinno, and Lierler (2020) championed a modular methodology for arguing program correctness. We show how a recently proposed many-sorted semantics for logic programs with aggregates allows us to apply their methodology to this type of program. This is illustrated using well-known encodings for the Graph Coloring and Traveling Salesman problems. In particular, we showcase how this modular approach allows us to reuse the proof of correctness of a Hamiltonian Cycle encoding studied in a previous publication when considering the Traveling Salesman program. 

   more » « less
3. The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP

   https://doi.org/10.1287/moor.2022.1265  

   Gutekunst, Samuel C; Williamson, David P (February 2023, Mathematics of Operations Research)

   Facet-defining inequalities of the symmetric traveling salesman problem (TSP) polytope play a prominent role in both polyhedral TSP research and state-of-the-art TSP solvers. In this paper, we introduce a new class of facet-defining inequalities, the circlet inequalities. These inequalities were first conjectured in Gutekunst and Williamson [Gutekunst SC, Williamson DP (2019) Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem. SIAM J. Discrete Math. 33(4):2452–2478] when studying the circulant TSP, and they provide a bridge between polyhedral TSP research and number-theoretic investigations of Hamiltonian cycles stemming from a conjecture from Marco Buratti in 2007. The circlet inequalities exhibit circulant symmetry by placing the same weight on all edges of a given length; our main proof exploits this symmetry to prove the validity of the circlet inequalities. We then show that the circlet inequalities are facet-defining and compute their strength following Goemans [Goemans MX (1995) Worst-case comparison of valid inequalities for the TSP. Math. Programming 69:335–349]; they achieve the same worst case strength as the similarly circulant crown inequalities of Naddef and Rinaldi [Naddef D, Rinaldi G (1992) The crown inequalities for the symmetric traveling salesman polytope. Math. Oper. Res. 17(2):308–326] but are generally stronger. Funding: This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program [Grant DGE-1650441] and by the National Science Foundation Division of Computing and Communications Foundations [Grant CCF-1908517]. 

   more » « less
4. Semi-boustrophedon coverage with a dubins vehicle

   https://doi.org/10.1109/IROS.2017.8206451  

   Lewis, Jeremy S.; Edwards, William; Benson, Kelly; Rekleitis, Ioannis; O'Kane, Jason M. (September 2017, IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS))

   This paper addresses the problem of generating coverage paths-that is, paths that pass within some sensor footprint of every point in an environment-for vehicles with Dubins motion constraints. We extend previous work that solves this coverage problem as a traveling salesman problem (TSP) by introducing a practical heuristic algorithm to reduce runtime while maintaining near-optimal path length. Furthermore, we show that generating an optimal coverage path is NP-hard by reducing from the Exact Cover problem, which provides justification for our algorithm's conversion of Dubins coverage instances to TSP instances. Extensive experiments demonstrate that the algorithm does indeed produce length paths comparable to optimal in significantly less time. 

   more » « less
5. Revisiting Data Collection in Robotic Sensor Networks: A Budget-Constrained Traveling Salesman Perspective

   Patil, Soham; Chen, Yutian; Tang, Bin (September 2024, IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2024))

   We focus on robotic sensor networks (RSNs), wherein mobile data collectors or robots are dispatched into the sensor field to collect data from the sensor nodes, and study a new algorithmic problem called battery-constrained data collection in RSNs (BC-DCR). Given an RSN of sensor nodes with varying numbers of sensory data packets to be collected and a robot with limited battery power, the goal of the BC-DCR is to dispatch the robot into the sensor field to collect the maximum number of data packets before it runs out of battery power and returns to the depot for recharging. Although extensive research has been conducted to achieve various performance objectives of data collection in RSNs, not much work has focused on the robot’s limited battery power. It is critical to consider the robot’s limited battery power to optimize the data-collecting performance of a large-scale RSN. We show that at the core of the BC-DCR is a new variation of the classic traveling salesman problem called the Budget-Constrained Traveling Salesman Problem (BC-TSP), which has not been adequately solved. We design an Integer Linear Programming (ILP)–based optimal algorithm and a time- efficient iterative greedy algorithm to solve the BC-TSP. Via extensive simulations using real measurements of battery power and mobility models of robots, we show that a) our algorithms outperform the existing work by collecting 29.1% more packets with the same battery power of the robots and b) our BC-TSP- based approach achieves 32.02% more network lifetime of the RSN compared to the existing approach. 

   more » « less