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.

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.

The capacitated vertex k-center problem receives as input a complete weighted graph and a set of capacity constraints. Its goal is to find a set of k centers and an assignment of vertices that does not violate the capacity constraints. Furthermore, the distance from the farthest vertex to its assigned center has to be minimized. The capacitated vertex k-center problem models real situations where a maximum number of clients must be assigned to centers and the travel time or distance from the clients to their assigned center has to be minimized. These centers might be hospitals, schools, police stations, among many others. The goal of this paper is to explicitly state how the capacitated vertex k-center problem and the minimum capacitated dominating set problem are related. We present an exact algorithm that consists of solving a series of integer programming formulations equivalent to the minimum capacitated dominating set problem over the bottleneck input graph. Lastly, we present an empirical evaluation of the proposed algorithm using off-the-shelf optimization software.

The uniform capacitated vertex k -center problem is an ???????? -hard combinatorial optimization problem that models real situations where k centers can only attend a maximum number of customers, and the travel time or distance from the customers to their assigned center has to be minimized. This article introduces a polynomial-time constructive heuristic algorithm that exploits the relationship between this problem and the minimum capacitated dominating set problem. The proposed heuristic is based on the one-hop farthest-first heuristic that has proven effective for the uncapacitated version of the problem. We carried out different empirical evaluations of the proposed heuristic, including an analysis of the effect of a parallel implementation of the algorithm, which significantly improved the running time for relatively large instances.

Water Stress Challenges: Mathematical Modeling of Water Resource Management

The Hamiltonian p-median problem (HpMP) generalizes the classical traveling salesperson (TSP) and the Hamiltonian cycle problems. The HpMP aims to find a collection of p non-intersecting cycles that span all the vertices of a given edge-weighted graph $G=(V,E,w)$ while minimizing the sum of the costs of the cycles. This paper introduces a memetic algorithm (MA) with explicit diversity management for the upper-bounded HpMP (UB-HpMP), where upper-bounded means that each cycle in the solution cannot exceed a maximum number of vertices. This MA approaches the problem as a set-partitioning problem, where each cluster of the partition contains the vertices of each cycle. Moreover, it uses a novel crossover operator based on the Hungarian algorithm, exploits the Lin–Kernighan heuristic, a state-of-the-art algorithm for the TSP, and uses best-non-penalized (BNP) selection to explicitly manage the population’s diversity. The proposed MA is tested against state-of-the-art algorithms and classical techniques, including those with and without implicit diversity management, as well as an open-source heuristic solver. The computational experimentation results show that explicit diversity management has advantages over other techniques.