FPT-algorithms for some problems related to integer programming |
| |
| Authors: | D. V. Gribanov D. S. Malyshev P. M. Pardalos S. I. Veselov |
| |
| Affiliation: | 1.School of Mathematics and Statistics,Xi’an Jiaotong University,Xi’an,People’s Republic of China;2.Beijing Center for Mathematics and Information Interdisciplinary Sciences,Beijing,People’s Republic of China;3.School of Management,Xi’an Jiaotong University,Xi’an,People’s Republic of China;4.The State Key Lab for Manufacturing Systems Engineering,Xi’an,People’s Republic of China |
| |
| Abstract: | This paper studies a new version of the location problem called the mixed center location problem. Let P be a set of n points in the plane. We first consider the mixed 2-center problem, where one of the centers must be in P, and we solve it in (O(n^2log n)) time. Second, we consider the mixed k-center problem, where m of the centers are in P, and we solve it in (O(n^{m+O(sqrt{k-m})})) time. Motivated by two practical constraints, we propose two variations of the problem. Third, we present a 2-approximation algorithm and three heuristics solving the mixed k-center problem ((k>2)). |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
