A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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 Um algoritmo de aproximação para o problema de 2 dispersões

Kazuyuki AMANO, Shin-ichi NAKANO

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Deixei P ser um conjunto de pontos no plano, e d(p, q) seja a distância entre um par de pontos p, q in P. Por um ponto pP e um subconjunto S ⊂ P com |S|≥3, o custo de 2 dispersão, denotado por custo2(p, S), de p em relação a S é a soma de (1) a distância de p para o ponto mais próximo Ssetminus{p} e (2) a distância de p para o segundo ponto mais próximo Ssetminus{p}. O custo de 2 dispersões custo2(S) do S ⊂ P com |S|≥3 é mínimop∈S{custo2(p, S)}. Dado um conjunto P of n pontos e um número inteiro k queremos calcular k subconjunto de pontos S of P com máximo custo2(S). Neste artigo, fornecemos um algoritmo de aproximação 1/({4sqrt{3}}) simples para o problema.

Publicação
IEICE TRANSACTIONS on Information Vol.E103-D No.3 pp.506-508
Data de publicação
2020/03/01
Publicitada
2019/11/28
ISSN online
1745-1361
DOI
10.1587/transinf.2019FCP0005
Tipo de Manuscrito
Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
Categoria

autores

Kazuyuki AMANO
  Gunma University
Shin-ichi NAKANO
  Gunma University

Palavra-chave