E-resources
Peer reviewed
Open access
-
ARAKI, Tetsuya; NAKANO, Shin-ichi
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2024, 2024-00-00Journal Article
The dispersion problem is a variant of facility location problems, that has been extensively studied. Given a polygon with n edges on a plane we want to find k points in the polygon so that the minimum pairwise Euclidean distance of the k points is maximized. We call the problem the k-dispersion problem in a polygon. Intuitively, for an island, we want to locate k drone bases far away from each other in flying distance to avoid congestion in the sky. In this paper, we give a polynomial-time approximation scheme (PTAS) for this problem when k is a constant and ε < 1 (where ε is a positive real number). Our proposed algorithm runs in O(((1/ε)2 + n/ε)k) time with 1/(1 + ε) approximation, the first PTAS developed for this problem. Additionally, we consider three variations of the dispersion problem and design a PTAS for each of them.
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
If the library membership card is not in the list,
add a new one.
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|
Source: Personal bibliographies
and: SICRIS
The material is available in full text. If you wish to order the material anyway, click the Continue button.