Improved approximation algorithms for capacitated fault-tolerant \(k\)-center.

*(English)*Zbl 1408.68033Given 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.

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.

Reviewer: Fevzi Belli (Paderborn)

##### 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 |

##### Keywords:

capacitated \(k\)-center problem; fault tolerance; approximation algorithm; non-uniform capacities; linear programming; LP rounding; minimax problem
PDF
BibTeX
XML
Cite

\textit{C. G. Fernandes} et al., Algorithmica 80, No. 3, 1041--1072 (2018; Zbl 1408.68033)

Full Text:
DOI

##### References:

[1] | Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York (1979) · Zbl 0411.68039 |

[2] | 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 |

[3] | Gonzalez, TF, Clustering to minimize the maximum intercluster distance, Theoret. Comput. Sci., 38, 293-306, (1985) · Zbl 0567.62048 |

[4] | Hochbaum, DS; Shmoys, DB, A best possible heuristic for the \(k\)-center problem, Math. Oper. Res., 10, 180-184, (1985) · Zbl 0565.90015 |

[5] | Hochbaum, DS; Shmoys, DB, A unified approach to approximation algorithms for bottleneck problems, J. ACM, 33, 533-550, (1986) |

[6] | Hsu, WL; Nemhauser, GL, Easy and hard bottleneck location problems, Discr. Appl. Math., 1, 209-215, (1979) · Zbl 0424.90049 |

[7] | Bar-Ilan, J; Kortsarz, G; Peleg, D, How to allocate network centers, J. Algorithms, 15, 385-415, (1993) · Zbl 0784.68012 |

[8] | Khuller, S; Sussmann, YJ, The capacitated \(k\)-center problem, SIAM J. Discr. Math., 13, 403-418, (2000) · Zbl 0947.05073 |

[9] | 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 |

[10] | 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 |

[11] | 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 |

[12] | Krumke, S, On a generalization of the \(p\)-center problem, Inf. Process. Lett., 56, 67-71, (1995) |

[13] | Chaudhuri, S; Garg, N; Ravi, R, The \(p\)-neighbor \(k\)-center problem, Inf. Process. Lett., 65, 131-134, (1998) · Zbl 1338.68290 |

[14] | Khuller, S; Pless, R; Sussmann, YJ, Fault tolerant \(k\)-center problems, Theoret. Comput. Sci., 242, 237-245, (2000) · Zbl 0944.68141 |

[15] | Chechik, S; Peleg, D, The fault-tolerant capacitated k-center problem, Theoret. Comput. Sci., 566, 12-25, (2015) · Zbl 1317.68135 |

[16] | Hall, P, On representatives of subsets, J. Lond. Math. Soc., 10, 26-30, (1935) · JFM 61.0067.01 |

[17] | Schrijver, A.: Theory of Linear and Integer Programming. Wiley Series in Discrete Mathematics & Optimization. Wiley, New York (1998) · Zbl 0970.90052 |

[18] | 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 |

[19] | Downey, RG; Fellows, MR, Fixed-parameter tractability and completeness II: on completeness for \(W[1]\), 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.