Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

An Approximation Algorithm for the 2-Dispersion Problem Algoritma Penghampiran untuk Masalah 2-Penyebaran

Kazuyuki AMANO, Shin-ichi NAKANO

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

Mari P menjadi satu set mata pada satah, dan d(p, q) ialah jarak antara sepasang mata p, q in P. Untuk satu titik pP dan subset S ⊂ P dengan |S|≥3, kos 2 penyebaran, dilambangkan dengan kos2(p, S), daripada p berkenaan dengan S ialah hasil tambah (1) jarak dari p ke titik terdekat dalam Ssetminus{p} dan (2) jarak dari p ke titik kedua terdekat dalam Ssetminus{p}. Kos 2 penyebaran kos2(S) daripada S ⊂ P dengan |S|≥3 ialah minp∈S{kos2(p, S)}. Diberi satu set P of n mata dan integer k kami ingin mengira k subset titik S of P dengan maksimum kos2(S). Dalam kertas ini kami memberikan algoritma penghampiran 1/({4sqrt{3}}) mudah untuk masalah itu.

Jawatankuasa
IEICE TRANSACTIONS on Information Vol.E103-D No.3 pp.506-508
Tarikh penerbitan
2020/03/01
Diumumkan
2019/11/28
ISSN dalam talian
1745-1361
DOI
10.1587/transinf.2019FCP0005
Jenis Manuskrip
Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
kategori

Pengarang

Kazuyuki AMANO
  Gunma University
Shin-ichi NAKANO
  Gunma University

Kata kunci

Contents [show]