## Yen Hung Chen - Approximability results for the $p$-centdian and the converse centdian problems

dmtcs:6877 - Discrete Mathematics & Theoretical Computer Science, November 30, 2022, vol. 24, no 2 - https://doi.org/10.46298/dmtcs.6877
Approximability results for the $p$-centdian and the converse centdian problems

Authors: Yen Hung Chen

Given an undirected graph $G=(V,E)$ with a nonnegative edge length function and an integer $p$, $0 < p < |V|$, the $p$-centdian problem is to find $p$ vertices (called the {\it centdian set}) of $V$ such that the {\it eccentricity} plus {\it median-distance} is minimized, in which the {\it eccentricity} is the maximum (length) distance of all vertices to their nearest {\it centdian set} and the {\it median-distance} is the total (length) distance of all vertices to their nearest {\it centdian set}. The {\it eccentricity} plus {\it median-distance} is called the {\it centdian-distance}. The purpose of the $p$-centdian problem is to find $p$ open facilities (servers) which satisfy the quality-of-service of the minimum total distance ({\it median-distance}) and the maximum distance ({\it eccentricity}) to their service customers, simultaneously. If we converse the two criteria, that is given the bound of the {\it centdian-distance} and the objective function is to minimize the cardinality of the {\it centdian set}, this problem is called the converse centdian problem. In this paper, we prove the $p$-centdian problem is NP-Complete. Then we design the first non-trivial brute force exact algorithms for the $p$-centdian problem and the converse centdian problem, respectively. Finally, we design two approximation algorithms for both problems.

Volume: vol. 24, no 2
Section: Discrete Algorithms
Published on: November 30, 2022
Accepted on: October 15, 2022
Submitted on: November 3, 2020
Keywords: Mathematics - Combinatorics,Computer Science - Computational Complexity,Computer Science - Data Structures and Algorithms