More Like this

1. On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem

   https://doi.org/10.4230/LIPIcs.SoCG.2022.2  

   Afshani, Peyman ; de Berg, Mark ; Buchin, Kevin ; Gao, Jie ; L ; Nayyeri, Amir ; Raichel, Benjamin ; Sarkar, Rik ; Wang, Haotian ; Yang, Hao-Tsung ( January 2022 , International Symposium on Computational Geometry (SOCG))

   Goaoc, Xavier ; Kerber, Michael (Ed.)

   We consider the following surveillance problem: Given a set P of n sites in a metric space and a set R of k robots with the same maximum speed, compute a patrol schedule of minimum latency for the robots. Here a patrol schedule specifies for each robot an infinite sequence of sites to visit (in the given order) and the latency L of a schedule is the maximum latency of any site, where the latency of a site s is the supremum of the lengths of the time intervals between consecutive visits to s. When k = 1 the problem is equivalent to the travelling salesman problem (TSP) and thus it is NP-hard. For k ≥ 2 (which is the version we are interested in) the problem becomes even more challenging; for example, it is not even clear if the decision version of the problem is decidable, in particular in the Euclidean case. We have two main results. We consider cyclic solutions in which the set of sites must be partitioned into 𝓁 groups, for some 𝓁 ≤ k, and each group is assigned a subset of the robots that move along the travelling salesman tour of the group atmore »equal distance from each other. Our first main result is that approximating the optimal latency of the class of cyclic solutions can be reduced to approximating the optimal travelling salesman tour on some input, with only a 1+ε factor loss in the approximation factor and an O((k/ε) ^k) factor loss in the runtime, for any ε > 0. Our second main result shows that an optimal cyclic solution is a 2(1-1/k)-approximation of the overall optimal solution. Note that for k = 2 this implies that an optimal cyclic solution is optimal overall. We conjecture that this is true for k ≥ 3 as well. The results have a number of consequences. For the Euclidean version of the problem, for instance, combining our results with known results on Euclidean TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields a (2(1-1/k)+ε)-approximation of the optimal unrestricted (not necessarily cyclic) solution. If the conjecture mentioned above is true, then our algorithm is actually a PTAS for the general problem in the Euclidean setting. Similar results can be obtained by combining our results with other known TSP algorithms in non-Euclidean metrics.« less
2. Diversity in Kemeny Rank Aggregation: A Parameterized Approach

   https://doi.org/10.24963/ijcai.2021/2  

   Arrighi, Emmanuel ; Fernau, Henning ; Lokshtanov, Daniel ; de Oliveira Oliveira, Mateus ; Wolf, Petra ( August 2021 , Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence)

   In its most traditional setting, the main concern of optimization theory is the search for optimal solutions for instances of a given computational problem. A recent trend of research in artificial intelligence, called solution diversity, has focused on the development of notions of optimality that may be more appropriate in settings where subjectivity is essential. The idea is that instead of aiming at the development of algorithms that output a single optimal solution, the goal is to investigate algorithms that output a small set of sufficiently good solutions that are sufficiently diverse from one another. In this way, the user has the opportunity to choose the solution that is most appropriate to the context at hand. It also displays the richness of the solution space.When combined with techniques from parameterized complexity theory, the paradigm of diversity of solutions offers a powerful algorithmic framework to address problems of practical relevance. In this work, we investigate the impact of this combination in the field of Kemeny Rank Aggregation, a well-studied class of problems lying in the intersection of order theory and social choice theory and also in the field of order theory itself. In particular, we show that KRA is fixed-parameter tractablemore »with respect to natural parameters providing natural formalizations of the notions of diversity and of the notion of a sufficiently good solution. Our main results work both when considering the traditional setting of aggregation over linearly ordered votes, and in the more general setting where votes are partially ordered.<« less
3. Decoupling Simulation Accuracy from Mesh Quality

   Schneider, Teseo ; Hu, Yixin ; Dumas, Jeremie ; Gao, Xifeng ; Panozzo, Daniele ; Zorin, Denis ( December 2018 , ACM transactions on graphics)

   For a given PDE problem, three main factors affect the accuracy of FEM solutions: basis order, mesh resolution, and mesh element quality. The first two factors are easy to control, while controlling element shape quality is a challenge, with fundamental limitations on what can be achieved. We propose to use p-refinement (increasing element degree) to decouple the approximation error of the finite element method from the domain mesh quality for elliptic PDEs. Our technique produces an accurate solution even on meshes with badly shaped elements, with a slightly higher running time due to the higher cost of high-order elements. We demonstrate that it is able to automatically adapt the basis to badly shaped elements, ensuring an error consistent with high-quality meshing, without any per-mesh parameter tuning. Our construction reduces to traditional fixed-degree FEM methods on high-quality meshes with identical performance. Our construction decreases the burden on meshing algorithms, reducing the need for often expensive mesh optimization and automatically compensates for badly shaped elements, which are present due to boundary con- straints or limitations of current meshing methods. By tackling mesh gen- eration and finite element simulation jointly, we obtain a pipeline that is both more efficient and more robust thanmore »combinations of existing state of the art meshing and FEM algorithms.« less
4. Gevrey estimates for asymptotic expansions of Tori in weakly dissipative systems*

   https://doi.org/10.1088/1361-6544/ac5cd5  

   Bustamante, Adrián P ; De la Llave, Rafael ( May 2022 , Nonlinearity)

   Abstract We consider a singular perturbation for a family of analytic symplectic maps of the annulus possessing a KAM torus. The perturbation introduces dissipation and contains an adjustable parameter. By choosing the adjustable parameter, one can ensure that the torus persists under perturbation. Such models are common in celestial mechanics. In field theory, the adjustable parameter is called the counterterm and in celestial mechanics, the drift . It is known that there are formal expansions in powers of the perturbation both for the quasi-periodic solution and the counterterm. We prove that the asymptotic expansions for the quasiperiodic solutions and the counterterm satisfy Gevrey estimates. That is, the n th term of the expansion is bounded by a power of n !. The Gevrey class (the power of n !) depends only on the Diophantine condition of the frequency and the order of the friction coefficient in powers of the perturbative parameter. The method of proof we introduce may be of interest beyond the problem considered here. We consider a modified Newton method in a space of power expansions. As is custumary in KAM theory, each step of the method is estimated in a smaller domain. In contrast with the KAMmore »results, the domains where we control the Newton method shrink very fast and the Newton method does not prove that the solutions are analytic. On the other hand, by examining carefully the process, we can obtain estimates on the coefficients of the expansions and conclude the series are Gevrey.« less
5. Safety-Aware Optimal Control of Stochastic Systems Using Conditional Value-at-Risk

   https://doi.org/10.23919/ACC.2018.8430957  

   Samuelson, Samantha ; Yang, Insoon ( June 2018 , 2018 Annual American Control Conference (ACC))

   In this paper, we consider a multi-objective control problem for stochastic systems that seeks to minimize a cost of interest while ensuring safety. We introduce a novel measure of safety risk using the conditional value-at-risk and a set distance to formulate a safety risk-constrained optimal control problem. Our reformulation method using an extremal representation of the safety risk measure provides a computationally tractable dynamic programming solution. A useful byproduct of the proposed solution is the notion of a risk-constrained safe set, which is a new stochastic safety verification tool. We also establish useful connections between the risk-constrained safe sets and the popular probabilistic safe sets. The tradeoff between the risk tolerance and the mean performance of our controller is examined through an inventory control problem.