The Freeze-Tag Problem (FTP) is the task of scheduling the activation of a robot swarm. The input consists of the initial locations of a set of mobile robots in some metric space. A single robot is initially “active” while the others are initially “frozen”. Active robots can move at unit speed, and upon reaching the location of a frozen robot, the latter is activated. The goal is to activate all the robots within the minimum time, minimizing the so-called makespan of the schedule. The complexity of this problem in Euclidean spaces was open until 2017, when Abel et al. [1] proved that FTP is NP-hard in the Euclidean plane with L2 distance. During that same year, Demaine and Rudoy [2] showed that it is also NP-hard in 3D Euclidean space with Lp distance for any p > 1, but left open the case with p = 1. This paper closes this gap and shows that FTP is indeed NP-hard in 3D Euclidean space with L1 distance. Furthermore, the hardness result holds in the strong sense, such that every coordinate is a rational bounded by a polynomial in the instance size.

We present the Positional Knapsack Problem (PKP), show that it is NP-hard and admits a Fully Polynomial-Time Approximation Scheme (FPTAS). This problem is a variant of the classical Binary Knapsack Problem (KP) in which the contribution of an item to the objective function varies according to the position in which it is added. The change in the valuation adds new properties to the problem that do not hold for KP as PKP is not a generalization of KP. Our FPTAS is based on a dynamic programming algorithm and uses a recursive rounding approach, which is necessary since the objective function depends on each item's value and position.

The Cable-Trench Problem (CTP) is a common generalization of the Single-Source Shortest Paths Problem (SSSP) and the Minimum Spanning Tree Problem (MST): given an edge-weighted graph with a special root vertex and parameters τ , γ ≥ 0 , the goal is to find a spanning tree that minimizes the total edge costs plus the total cost of the paths from each vertex to the root, scaled by τ and γ , respectively. While it is well known that both SSSP and MST can be solved in polynomial time, CTP is NP -hard. We show that computing an approximate solution with factor less than 1.000475 is NP -hard, thus ruling out a polynomial-time approximation scheme, unless P = NP . We also consider the more general Steiner Cable-Trench Problem (SCTP), for which only a given subset of terminal vertices must be spanned by a solution. The tree might include non-terminal vertices, known as Steiner vertices, although only paths from terminals to the root are considered in the total cost. For this problem, we present a ( 2 . 88 + ϵ ) -approximation based on a counting argument, for any ϵ > 0 ; also, we give a simple parameterized algorithm with the number of terminals as parameter.

In the Star k-Hub Center (SkHC), given a connected edge-weighted graph G, a center c ε V(G) and integers k, r > 0, one wants to select a set of hubs H ⊆ V(G)\{c} of size k and an assignment from vertices to hubs. The goal is to find a solution in which the length of the longest path connecting each pair of vertices through the assigned hubs and the center is at most r. This problem appears in many areas, such as telecommunication, aviation and logistics, where hubs represent cross-docking centers that consolidate demand between pairs of clients, and the network has a centralized design. This paper investigates the parameterized complexity of the underlying graph connectivity problem. First, we note that finding a (1.25 - ε-approximation is W[2]-hard, for ε> 0, when the parameter is the number of hubs k. Moreover, we show that the problem is W[1]-hard even when parameterized by k plus the vertex cover number of the graph. While this rules out an algorithm parameterized by the treewidth tw of the graph, as a positive result, we present an efficient parameterized approximation scheme. Namely, for every ε> 0, we have a (1 + ε-approximation that runs in time 0*((tw/e)0(tw)).

The Cable-Trench Problem (CTP) is an optimization problem that generalizes both the Single-Destination Shortest Path Problem and the Minimum Spanning Tree Problem. Given an edge weighted graph with a special root vertex and parameters τ, γ ≥ 0, the objective is to find a rooted spanning tree that minimizes the weight of the tree, scaled by τ, plus the sum of the weights over all shortest paths from the root, scaled by γ. While each of the generalized problems are well-known to be polynomial-time solvable, CTP is NP-hard. In this paper, we show that even finding an approximation with factor of 1.000475 is NP-hard, thus ruling out the existence of a polynomial-time approximation scheme, unless P = NP.

In the classical Travelling Salesman Problem (TSP), one wants to find a route that visits a set of n cities, such that the total travelled distance is minimum. An often considered generalization is the Travelling Car Renter Problem (CaRS), in which the route is travelled by renting a set of cars and the cost to travel between two given cities depends on the car that is used. The car renter may choose to swap vehicles at any city, but must pay a fee to return the car to its pickup location. This problem appears in logistics and urban transportation when the vehicles can be provided by multiple companies, such as in the tourism sector. In this paper, we consider the case in which the return fee is some fixed number g >= 0, which we call the Uniform CaRS (UCaRS). We show that, already for this version, there is no o(log n)-approximation algorithm unless P = NP. The main contribution is an O(log n)-approximation algorithm for the problem, which is based on the randomized rounding of an exponentially large LP-relaxation.

A bond of a graph G is an inclusion-wise minimal disconnecting set of G, i.e., bonds are cut-sets that determine cuts [S,V\S] of G such that G[S] and G[V\S] are both connected. Given s,t in V(G), an st-bond of G is a bond whose removal disconnects s and t. Contrasting with the large number of studies related to maximum cuts, there are very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond and the largest st-bond of a graph. Although cuts and bonds are similar, we remark that computing the largest bond of a graph tends to be harder than computing its maximum cut. We show that Largest Bond remains NP-hard even for planar bipartite graphs, and it does not admit a constant-factor approximation algorithm, unless P = NP. We also show that Largest Bond and Largest st-Bond on graphs of clique-width w cannot be solved in time f(w) x n^{o(w)} unless the Exponential Time Hypothesis fails, but they can be solved in time f(w) x n^{O(w)}. In addition, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, but they do not admit polynomial kernels unless NP subseteq coNP/poly.

Recently, many cities are facing challenging mobility and safety issues. The former is commonly related to traffic congestion, as a consequence of uncontrolled population growth and accelerated urbanization. The latter regards to elevated number of city-wide criminal incidents. Several Intelligent Transportation Systems (ITS) were proposed to overcome mobility issues; meanwhile, some safety- based systems were proposed to guide pedestrians and drivers toward safest paths. However, most of these systems tackle only one of the issues. Hence, an ITS can guide vehicles toward risky areas, in order to avoid traffic congestion, while a safety-based system can guide them toward congested roads, focusing on the safety of drivers and passengers. This paper introduces itsSAFE (Intelligent Transportation Systems for improving SAfety and traFfic Efficiency), an ITS which employs accurate knowledge about traffic conditions and unsafety levels on roads for improving the safety of drivers and passengers at the same time it deals with traffic congestion. Simulation results under a realistic scenario have shown that itsSAFE outperformed state-of-the-art approaches that deal with mobility or safety issues, by effectively dealing with traffic efficiency and safety.

We consider the supply chain problem of minimizing ordering, distribution, and inventory holding costs of a supply chain formed by a set of warehouses and retailers over a finite time horizon, which we call the production and distribution problem. This is a common generalization of the classical metric facility location problem and joint replenishment problem that coordinates the network design and inventory management decisions in an integrated manner. This coordination can represent significant economy for many applications, where network design and operational costs are normally considered separately. This problem is considered when the instances satisfy assumptions such as metric space of warehouse and retailer locations, and monotonic increasing inventory holding costs. In this work, we give a 2.77-approximation based on the randomized rounding of the natural mixed-integer programming relaxation. Also, we give a 5-approximation for the case that objective function includes retailer ordering setup costs.

SUMMARY The automatic generation of test suites for systems modelled as finite state machines (FSMs) is an important problem that impacts several critical applications. Known methods that automatically generate tests for FSMs, specially the W‐method and some derivations, strongly assume that the number of system states is small. If the overall number of states in the FSM specification is relatively large, such methods become difficult to use. However, often in practice, a system is defined as a combination of several subsystems, with the latter already independently designed, developed and tested. In this paper, we define the concept of combined FSMs and introduce a new method to test modular compositions of FSMs. This method allows for a new incremental testing strategy that turns the testing of new systems into a much more scalable process. As an example, we present an infinite family of naturally occurring FSM models for which our method produces exponentially more compact test suites than the W‐method. Copyright © 2012 John Wiley & Sons, Ltd.