In the Directed Latency problem, we are given an asymmetric metric space (V ∪ {s},c) on a set V of clients and a depot s. We are looking for a path P starting in s that visits all clients and minimizes the sum of the clients’ waiting times (also known as latency) before being visited on the path. This models problems in logistics where client satisfaction is essential, as opposed to objectives like in TSP, where the goal is to make the salesperson as happy as possible.

One of the most elementary spreading models on graphs can be described by a fire spreading from a burning vertex in discrete time steps. At each step, all neighbors of burning vertices catch fire. A well-studied extension to model fire containment is to allow for fireproofing a number B of non-burning vertices at each step. Interestingly, basic computational questions about this model are computationally hard even on trees. One of the most prominent such examples is Resource Minimization for Fire Containment (RMFC), which asks how small B can be chosen so that a given subset of vertices will never catch fire. Despite recent progress on RMFC on trees, prior work left a significant gap in terms of its approximability. We close this gap by providing an optimal 2-approximation and an asymptotic PTAS, resolving two open questions in the literature. Both results are obtained in a unified way, by first designing a PTAS for a smooth variant of RMFC, which is obtained through a careful LP-guided enumeration procedure.

We revisit the a priori TSP (with independent activation) and prove stronger approximation guarantees than were previously known. In the a priori TSP, we are given a metric space $(V,c)$ and an activation probability $p(v)$ for each customer $v\in V$. We ask for a TSP tour $T$ for $V$ that minimizes the expected length after cutting $T$ short by skipping the inactive customers. All known approximation algorithms select a nonempty subset $S$ of the customers and construct a master route solution, consisting of a TSP tour for $S$ and two edges connecting every customer $v\in V\setminus S$ to a nearest customer in $S$. We address the following questions. If we randomly sample the subset $S$, what should be the sampling probabilities? How much worse than the optimum can the best master route solution be? The answers to these questions (we provide almost matching lower and upper bounds) lead to improved approximation guarantees: less than 3.1 with randomized sampling, and less than 5.9 with a deterministic polynomial-time algorithm.

We present a new approximation algorithm for the (metric) prize-collecting traveling salesperson problem (PCTSP). In PCTSP, opposed to the classical traveling salesperson problem (TSP), one may choose to not include a vertex of the input graph in the returned tour at the cost of a given vertex-dependent penalty, and the objective is to balance the length of the tour and the incurred penalties for omitted vertices by minimizing the sum of the two. We present an algorithm that achieves an approximation guarantee of 1.774 with respect to the natural linear programming relaxation of the problem. This significantly reduces the gap between the approximability of classical TSP and PCTSP, beating the previously best known approximation factor of 1.915. As a key ingredient of our improvement, we present a refined decomposition technique for solutions of the LP relaxation, and show how to leverage components of that decomposition as building blocks for our tours.