# zbMATH — the first resource for mathematics

Improved approximation algorithms for capacitated fault-tolerant $$k$$-center. (English) Zbl 1408.68033
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.

##### MSC:
 68M15 Reliability, testing and fault tolerance of networks and computer systems 68W25 Approximation algorithms 90B80 Discrete location and assignment 90C47 Minimax problems in mathematical programming
Full Text:
##### References:
  Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York (1979) · Zbl 0411.68039  Feder, T., Greene, D.: Optimal algorithms for approximate clustering. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 434-444 (1988). https://doi.org/10.1145/62212.62255  Gonzalez, TF, Clustering to minimize the maximum intercluster distance, Theoret. Comput. Sci., 38, 293-306, (1985) · Zbl 0567.62048  Hochbaum, DS; Shmoys, DB, A best possible heuristic for the $$k$$-center problem, Math. Oper. Res., 10, 180-184, (1985) · Zbl 0565.90015  Hochbaum, DS; Shmoys, DB, A unified approach to approximation algorithms for bottleneck problems, J. ACM, 33, 533-550, (1986)  Hsu, WL; Nemhauser, GL, Easy and hard bottleneck location problems, Discr. Appl. Math., 1, 209-215, (1979) · Zbl 0424.90049  Bar-Ilan, J; Kortsarz, G; Peleg, D, How to allocate network centers, J. Algorithms, 15, 385-415, (1993) · Zbl 0784.68012  Khuller, S; Sussmann, YJ, The capacitated $$k$$-center problem, SIAM J. Discr. Math., 13, 403-418, (2000) · Zbl 0947.05073  Cygan, M., Hajiaghayi, M., Khuller, S.: LP rounding for $$k$$-centers with non-uniform hard capacities. In: IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 273-282 (2012). https://doi.org/10.1109/FOCS.2012.63 · Zbl 0784.68012  An, HC; Bhaskara, A; Chekuri, C; Gupta, S; Madan, V; Svensson, O, Centrality of trees for capacitated $$k$$-center, Math. Program., 154, 29-53, (2015) · Zbl 1337.90036  Cygan, M., Kociumaka, T.: Constant factor approximation for capacitated $$k$$-center with outliers. In: 31st International Symposium on Theoretical Aspects of Computer Science, vol. 25, pp. 251-262 (2014). https://doi.org/10.4230/LIPIcs.STACS.2014.251 · Zbl 1359.90056  Krumke, S, On a generalization of the $$p$$-center problem, Inf. Process. Lett., 56, 67-71, (1995)  Chaudhuri, S; Garg, N; Ravi, R, The $$p$$-neighbor $$k$$-center problem, Inf. Process. Lett., 65, 131-134, (1998) · Zbl 1338.68290  Khuller, S; Pless, R; Sussmann, YJ, Fault tolerant $$k$$-center problems, Theoret. Comput. Sci., 242, 237-245, (2000) · Zbl 0944.68141  Chechik, S; Peleg, D, The fault-tolerant capacitated k-center problem, Theoret. Comput. Sci., 566, 12-25, (2015) · Zbl 1317.68135  Hall, P, On representatives of subsets, J. Lond. Math. Soc., 10, 26-30, (1935) · JFM 61.0067.01  Schrijver, A.: Theory of Linear and Integer Programming. Wiley Series in Discrete Mathematics & Optimization. Wiley, New York (1998) · Zbl 0970.90052  Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, pp. 85-103 (1972). https://doi.org/10.1007/978-1-4684-2001-2_9 · Zbl 0873.68059  Downey, RG; Fellows, MR, Fixed-parameter tractability and completeness II: on completeness for $$W$$, Theoret. Comput. Sci., 141, 109-131, (1995) · Zbl 0873.68059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.