An Approximation Algorithm for the 2-Dispersion Problem

• AMANO Kazuyuki

  Gunma University

• NAKANO Shin-ichi

  Gunma University

Abstract

Let P be a set of points on the plane, and d(p, q) be the distance between a pair of points p, q in P. For a point p∈P and a subset S ⊂ P with |S|≥3, the 2-dispersion cost, denoted by cost₂(p, S), of p with respect to S is the sum of (1) the distance from p to the nearest point in S\setminus{p} and (2) the distance from p to the second nearest point in S\setminus{p}. The 2-dispersion cost cost₂(S) of S ⊂ P with |S|≥3 is min_p∈S{cost₂(p, S)}. Given a set P of n points and an integer k we wish to compute k point subset S of P with maximum cost₂(S). In this paper we give a simple 1/({4\sqrt{3}}) approximation algorithm for the problem.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E103.D (3), 506-508, 2020-03-01

  The Institute of Electronics, Information and Communication Engineers

Keywords

• dispersion problem
• approximation algorithm

Details

• CRID: 1390565134832332928
• NII Article ID: 130007804167
• DOI: 10.1587/transinf.2019fcp0005
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E103.D/3/E103.D_2019FCP0005/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed