FPT-algorithms for some problems related to integer programming |
| |
| Authors: | D V Gribanov D S Malyshev P M Pardalos S I Veselov |
| |
| Institution: | 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^2\log 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 等数据库收录！ |
|
