Improved approximation algorithms for capacitated fault-tolerant \(k\)-center (Q1742378): Difference between revisions

Given a metric space \(V\) and a positive integer \(k\), a set of \(k\) centers are to be selected such that the maximum distance from an element of \(V\) to its closest center is minimized. The elements of set S are usually referred to as centers, and the elements of \(V\) as clients. This is the informal definition of \(k\)-Center which is an NP-complete minimax problem that is relevant to many application areas, for example, computer network systems. Imagine that \(V\) represents the nodes of a network that \(k\) routers are to be installed the way that the latency is minimized. Additional constraints are possible, for example the number of nodes a router can serve might be limited, given by its capacity. This defines the Capacitated \(k\)-Center. Also relevant for practice is the variant of \(k\)-Center that considers the case that centers may fail during operation. To enable the network to serve properly, clients are to be connected to a given minimum number of centers. Thus, \(\alpha\)-Fault-Tolerant \(k\)-Center considers the case that any subset of centers, in the worst case of size \(\alpha\), might fail, so that a client might have to be connected to the \((\alpha+1)\)-th center. The objective is to minimize the maximum distance from a client to the \(\alpha+1\) centers. Taking also the capacity of the nodes into consideration, the paper introduces well-thought-out approximations to Capacitated \(\alpha\)-Fault-Tolerant \(k\)-Center and Capacitated ``Conservative'' \(\alpha\)-Fault-Tolerant \(k\)-Center. The latter considers also an initial assignment of the nodes to servers as a solution. To deal with these problems, the authors suggest a strategy in two phases, starting with identifying clusters of vertices where an optimal solution has to install a minimum of \(\alpha\) centers with sufficient amount of redundant capacity for a reassignment in case of a failure. While the \(\alpha\) guessed centers of a cluster may not correspond to centers in an optimal solution, elements are selected that are near to centers of an optimal solution, leading to an approximate solution. The second phase deals with the residual instance, where a part of a solution is already known. This seems to work well as the carefully determined time complexities of the algorithms show. The authors use combinatorial algorithms and linear programming formulation to obtain their approximation. They partly use techniques known from the literature; nevertheless, the approach is, to my knowledge, novel, and can be used in combination with different methods and algorithms to be applied to practical problems of network systems. Moreover, the paper is easy to read and a comprehensive list of references might help also newcomers to access this interesting and relatively young research area.