We initiate the study of multipacking problems for geometric point sets with respect to their Euclidean distances. We consider a set of n points P and define \(N_s[v]\) as the subset of P that includes the s nearest points of \(v \in P\) and the point v itself. We assume that the s-th neighbor of each point is unique, for every \(s \in \{0, 1, 2, \dots , n-1\}\) . For a natural number \(r \le n\) , an r-multipacking is a set \( M \subseteq P \) such that for each point \( v \in P \) and for every integer \( 1\le s \le r \) , \(|N_s[v]\cap M|\le (s+1)/2\) . The r-multipacking number of P is the maximum cardinality of an r-multipacking of P and is denoted by \( {{\,\textrm{mp}\,}}_{r}(P) \) . For \(r=n-1\) , an r-multipacking is called a multipacking and r-multipacking number is called as multipacking number. We study the problem of computing a maximum r-multipacking for point sets in \(\mathbb {R}^2\) . We show that a maximum 1-multipacking can be computed in polynomial time but computing a maximum 2-multipacking is NP complete. Further, we provide approximation and parameterized solutions to the 2-multipacking problem.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Multipacking in the Euclidean Metric Space

  • Arun Kumar Das,
  • Sandip Das,
  • Sk Samim Islam,
  • Ritam Manna Mitra,
  • Bodhayan Roy

摘要

We initiate the study of multipacking problems for geometric point sets with respect to their Euclidean distances. We consider a set of n points P and define \(N_s[v]\) as the subset of P that includes the s nearest points of \(v \in P\) and the point v itself. We assume that the s-th neighbor of each point is unique, for every \(s \in \{0, 1, 2, \dots , n-1\}\) . For a natural number \(r \le n\) , an r-multipacking is a set \( M \subseteq P \) such that for each point \( v \in P \) and for every integer \( 1\le s \le r \) , \(|N_s[v]\cap M|\le (s+1)/2\) . The r-multipacking number of P is the maximum cardinality of an r-multipacking of P and is denoted by \( {{\,\textrm{mp}\,}}_{r}(P) \) . For \(r=n-1\) , an r-multipacking is called a multipacking and r-multipacking number is called as multipacking number. We study the problem of computing a maximum r-multipacking for point sets in \(\mathbb {R}^2\) . We show that a maximum 1-multipacking can be computed in polynomial time but computing a maximum 2-multipacking is NP complete. Further, we provide approximation and parameterized solutions to the 2-multipacking problem.