|
|||||
|
|
The Center Location Improvement Problem Under the Hamming Distance |
|
| Authors: | Binwu?Zhang |
| Institution: | (1) Department of Mathematics, Zhejiang University, Hangzhou, 310027, China;(2) Department of Mathematics and Physics, Hohai University, Changzhou Campus, Changzhou, 213022, China;(3) Department of Mathematics, City University of Hong Kong, Hong Kong, China |
| Abstract: | In this paper, we consider the center location improvement problems under the sum-type and bottleneck-type Hamming distance. For the sum-type problem, we show that achieving an algorithm with a worst-case ratio of O(log |V|) is NP-hard, and for the bottleneck-type problem, we present a strongly polynomial algorithm. |
| Keywords: | center location problem inapproximability Hamming distance |
| 本文献已被 SpringerLink 等数据库收录！ | |