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
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.
Tetsuya ARAKI
Gunma University
Hiroyuki MIYATA
Gunma University
Shin-ichi NAKANO
Gunma University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Tetsuya ARAKI, Hiroyuki MIYATA, Shin-ichi NAKANO, "Dispersion on Intervals" in IEICE TRANSACTIONS on Fundamentals,
vol. E105-A, no. 9, pp. 1181-1186, September 2022, doi: 10.1587/transfun.2021DMP0004.
Abstract: Given a set of n disjoint intervals on a line and an integer k, we want to find k points in the intervals so that the minimum pairwise distance of the k points is maximized. Intuitively, given a set of n disjoint time intervals on a timeline, each of which is a time span we are allowed to check something, and an integer k, which is the number of times we will check something, we plan k checking times so that the checks occur at equal time intervals as much as possible, that is, we want to maximize the minimum time interval between the k checking times. We call the problem the k-dispersion problem on intervals. If we need to choose exactly one point in each interval, so k=n, and the disjoint intervals are given in the sorted order on the line, then two O(n) time algorithms to solve the problem are known. In this paper we give the first O(n) time algorithm to solve the problem for any constant k. Our algorithm works even if the disjoint intervals are given in any (not sorted) order. If the disjoint intervals are given in the sorted order on the line, then, by slightly modifying the algorithm, one can solve the problem in O(log n) time. This is the first sublinear time algorithm to solve the problem. Also we show some results on the k-dispersion problem on disks, including an FPTAS.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021DMP0004/_p
Salinan
@ARTICLE{e105-a_9_1181,
author={Tetsuya ARAKI, Hiroyuki MIYATA, Shin-ichi NAKANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Dispersion on Intervals},
year={2022},
volume={E105-A},
number={9},
pages={1181-1186},
abstract={Given a set of n disjoint intervals on a line and an integer k, we want to find k points in the intervals so that the minimum pairwise distance of the k points is maximized. Intuitively, given a set of n disjoint time intervals on a timeline, each of which is a time span we are allowed to check something, and an integer k, which is the number of times we will check something, we plan k checking times so that the checks occur at equal time intervals as much as possible, that is, we want to maximize the minimum time interval between the k checking times. We call the problem the k-dispersion problem on intervals. If we need to choose exactly one point in each interval, so k=n, and the disjoint intervals are given in the sorted order on the line, then two O(n) time algorithms to solve the problem are known. In this paper we give the first O(n) time algorithm to solve the problem for any constant k. Our algorithm works even if the disjoint intervals are given in any (not sorted) order. If the disjoint intervals are given in the sorted order on the line, then, by slightly modifying the algorithm, one can solve the problem in O(log n) time. This is the first sublinear time algorithm to solve the problem. Also we show some results on the k-dispersion problem on disks, including an FPTAS.},
keywords={},
doi={10.1587/transfun.2021DMP0004},
ISSN={1745-1337},
month={September},}
Salinan
TY - JOUR
TI - Dispersion on Intervals
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1181
EP - 1186
AU - Tetsuya ARAKI
AU - Hiroyuki MIYATA
AU - Shin-ichi NAKANO
PY - 2022
DO - 10.1587/transfun.2021DMP0004
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E105-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2022
AB - Given a set of n disjoint intervals on a line and an integer k, we want to find k points in the intervals so that the minimum pairwise distance of the k points is maximized. Intuitively, given a set of n disjoint time intervals on a timeline, each of which is a time span we are allowed to check something, and an integer k, which is the number of times we will check something, we plan k checking times so that the checks occur at equal time intervals as much as possible, that is, we want to maximize the minimum time interval between the k checking times. We call the problem the k-dispersion problem on intervals. If we need to choose exactly one point in each interval, so k=n, and the disjoint intervals are given in the sorted order on the line, then two O(n) time algorithms to solve the problem are known. In this paper we give the first O(n) time algorithm to solve the problem for any constant k. Our algorithm works even if the disjoint intervals are given in any (not sorted) order. If the disjoint intervals are given in the sorted order on the line, then, by slightly modifying the algorithm, one can solve the problem in O(log n) time. This is the first sublinear time algorithm to solve the problem. Also we show some results on the k-dispersion problem on disks, including an FPTAS.
ER -