The vertex k-center problem is a classical NP-Hard optimization problem with application to Facility Location and Clustering among others. This problem consists in finding a subset C ⊆ V of an input graph G = (V, E), such that the distance from the farthest vertex in V to its nearest center in C is minimized, where ıCı <; k, with k ε Z± as part of the input. Many heuristics, metaheuristics, approximation algorithms, and exact algorithms have been developed for this problem. This paper presents an analytical study and experimental evaluation of the most representative approximation algorithms for the vertex k-center problem. For each of the algorithms under consideration and using a common notation, we present proofs of their corresponding approximation guarantees as well as examples of tight instances of such approximation bounds, including a novel tight example for a 3-approximation algorithm. Lastly, we present the results of extensive experiments performed over de facto benchmark data sets for the problem which includes instances of up to 71009 vertices.

Bad air quality due to free pollutants such as particulate matter (PM), carbon dioxide (CO ${}_2$ ), nitrogen oxides (NO ${}_x$ ) and volatile organic components (VOC) increases the risk of long- term health diseases. The impact of traffic-calming measures on air quality has been studied using specialized equipment at control sites or mounted on cars to monitor pollutants levels. However, this approach suffers from a large number of variables on the experiments such as vehicles types, number of monitored vehicles, driver’s behavior, traffic density, time of the day, elapsed monitoring time, road conditions and weather. In this work, we use a cellular automata and an instantaneous traffic emissions model to capture the effect of speed humps on traffic flow and on the generation of CO ${}_2$ , NO ${}_x$ , VOC and PM pollutants. This approach allows us to study and characterize the effect of many speed humps on a single lane. We found that speed humps significantly promote the generation of pollutants when the number of vehicles on a lane is low. Our results may provide insight into urban planning strategies to reduce the generation of traffic emissions and lower the risk of long-term health diseases.

The graph burning problem is an NP-hard combinatorial optimization problem that helps quantify the vulnerability of a graph to contagion. This paper introduces a simple farthest-first traversal-based approximation algorithm for this problem over general graphs. We refer to this proposal as the Burning Farthest-First (BFF) algorithm. BFF runs in O(n3) steps and has a tight approximation factor of 3-2/b(G), where b(G) is the size of an optimal solution. The main attribute of BFF is that it has a better approximation factor than the state-of-the-art approximation algorithms for general graphs, which report an approximation factor of 3. Despite being simple, BFF proved practical when tested over some benchmark datasets.

The graph burning problem is an NP-hard combinatorial optimization problem that helps quantify how vulnerable a graph is to contagion. This paper introduces three mathematical formulations of the problem: an integer linear program (ILP) and two constraint satisfaction problems (CSP1 and CSP2). Thanks to off-the-shelf optimization software, these formulations can be solved optimally over arbitrary graphs; this is relevant because the only algorithms designed to date for this problem are approximation algorithms and heuristics, which do not guarantee to find optimal solutions. We empirically compared the proposed formulations using random graphs and off-the-shelf optimization software. The results show that CSP1 and CSP2 tend to reach optimal solutions in less time than the ILP. Therefore, we executed them over some benchmark graphs of order at most 5908. The previously best-known solutions for some of these graphs were improved. We draw some empirical observations from the experimental results. For instance, we find the tendency: the larger the graph’s optimal solution, the more difficult it is to find it. Finally, the resulting set of optimal solutions might be helpful as a benchmark dataset for the performance evaluation of non-exact algorithms.

Multiple traveling salesperson problems (mTSP) are a collection of problems that generalize the classical traveling salesperson problem (TSP). In a nutshell, an mTSP variant seeks a minimum cost collection of m paths that visit all vertices of a given weighted complete graph. This paper introduces novel compact integer programs for the depot-free mTSP (DFmTSP). This fundamental variant models real scenarios where depots are unknown or unnecessary. The proposed integer programs are adapted to the main variants of the DFmTSP, such as closed paths, open paths, bounding constraints (also known as load balance), and the minsum and minmax objective functions. Some of these integer programs have $\mathcal{O}\left(n^{2}m\right)$ binary variables and $\mathcal{O}\left(n^2\right)$ constraints, where m is the number of salespersons and $n=\left|V\right(G\left)\right|$. Furthermore, we introduce more compact integer programs with $\mathcal{O}\left(n^2\right)$ binary variables and $\mathcal{O}\left(n^2\right)$ constraints for the same problem and most of its main variants. Without losing their compactness, all the proposed programs are adapted to fixed-destination multiple-depots mTSP (FD-MmTSP) and a combination of FD-MmTSP and DFmTSP, where fewer than m depots are part of the input, but the solution still consists of m paths. We used off-the-shelf optimization software to empirically test the proposed integer programs over a classical benchmark dataset; these tests show that the proposed programs meet desirable theoretical properties and have practical advantages over the state of the art.