We study the parity-constrained knapsack（PARKN） center problem. In a PARKN center instance, we are given a set of vertices, each associated with a non-negative weight and a parity requirement, which can be odd or even. These vertices are located in a metric space with distances, and a knapsack capacity is also given by a non-negative k. The goal of this problem is to select a subset of vertices whose total weight is less than or equal to the knapsack capacity k to serve as centers and assign each vertex to one of these centers so that the maximum distance from any vertex to its assigned center is minimized. Moreover, for each center, the number of vertices assigned to it must meet its parity requirement.

Our main contribution is a 10-approximation algorithm for the PARKN center problem, which is divided into three phases. The first phase employs the concept of the maximal independent set to determine an initial solution that selects a subset of centers under the knapsack capacity and assigns each vertex to a center. Consider that there may exist some centers whose parity requirement isn’t satisfied, we pair up these centers and modify the center set and assignments, respectively, in phase two and three to achieve a feasible solution.

韩璐，北京邮电大学副教授，博士生导师。主要研究方向为组合优化、近似算法。长期从事聚类和斯坦纳树问题的算法研究。主持完成国家自然科学基金项目1项，参与国家自然科学基金项目1项，参与北京市自然科学基金重点研究专题1项，发表论文20余篇。