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

Dispersion on Intervals Penyerakan pada Selang

Tetsuya ARAKI, Hiroyuki MIYATA, Shin-ichi NAKANO

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

Diberi satu set n selang putus pada garis dan integer k, kita nak cari k titik dalam selang supaya jarak pasangan minimum bagi k mata dimaksimumkan. Secara intuitif, diberikan satu set n selang masa terputus-putus pada garis masa, setiap satunya ialah jangka masa yang kita dibenarkan untuk menyemak sesuatu dan integer k, iaitu bilangan kali kami akan menyemak sesuatu, kami merancang k masa menyemak supaya semakan berlaku pada selang masa yang sama sebanyak mungkin, iaitu, kami ingin memaksimumkan selang masa minimum antara k masa menyemak. Kami memanggil masalah itu k-masalah penyebaran pada selang waktu. Jika kita perlu memilih tepat satu mata dalam setiap selang, jadi k=n, dan selang cerai diberikan dalam susunan yang diisih pada baris, kemudian dua O(n) algoritma masa untuk menyelesaikan masalah diketahui. Dalam makalah ini kami memberikan yang pertama O(n) algoritma masa untuk menyelesaikan masalah bagi sebarang pemalar k. Algoritma kami berfungsi walaupun selang cerai diberikan dalam mana-mana susunan (tidak diisih). Jika selang terputus diberikan dalam susunan yang disusun pada baris, maka, dengan mengubah sedikit algoritma, seseorang boleh menyelesaikan masalah dalam O(log n) masa. Ini adalah algoritma masa sublinear pertama untuk menyelesaikan masalah. Juga kami menunjukkan beberapa hasil pada k-masalah penyebaran pada cakera, termasuk FPTAS.

Jawatankuasa
IEICE TRANSACTIONS on Fundamentals Vol.E105-A No.9 pp.1181-1186
Tarikh penerbitan
2022/09/01
Diumumkan
2022/03/08
ISSN dalam talian
1745-1337
DOI
10.1587/transfun.2021DMP0004
Jenis Manuskrip
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
kategori
Algoritma dan Struktur Data

Pengarang

Tetsuya ARAKI
  Gunma University
Hiroyuki MIYATA
  Gunma University
Shin-ichi NAKANO
  Gunma University

Kata kunci

Contents [show]