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. Budget-Constrained Traveling Salesman Problem: a Cooperative Multi-Agent Reinforcement Learning Approach

   https://doi.org/10.1109/SECON64284.2024.10934896  

   Mak, King To; Gonzalez, Christopher; Magnaye, Zari; Gonzalez, Jessica; Chen, Yutian; Tang, Bin (December 2024, IEEE)

   We study a new variation of the Traveling Salesman Problem (TSP) called the Budget-Constrained Traveling Salesman Problem (BC-TSP). BC-TSP is inspired by a few emerging network applications, such as robotic sensor networks. We design a prize-driven multi-agent reinforcement learning (MARL) framework to solve the BC-TSP. The main novelty of the framework, named P-MARL, is that it makes a connection between the prize maximization in BC-TSP and the cumulative reward maximization in reinforcement learning (RL) to design a more efficient MARL algorithm. In particular, P-MARL integrates the prizes available at nodes into the reward model of the MARL to guide the cooperative effort of multiple learning agents. Via extensive simulations using synthetic data of state capital cities of the U.S., we show that a) the P-MARL outperforms the existing prize-oblivious MARL work by collecting 28.8 % of more prizes under the same budget constraints, b) it takes two orders of magnitudes of shorter training time than the state-of-the-art deep reinforcement learning-based approach while collecting 45.3 % more prizes under the same budgets, and c) P-MARL collects prizes at least 91.9% of optimal obtained by the Integer Linear Programming (ILP) under different network parameters. 

   more » « less