IEICE TRANSACTIONS on Fundamentals
Faster Min-Max r-Gatherings
Summary :
An r-gathering of customers C to facilities F is an assignment A of C to open facilities F' ⊂ F such that r (≥ 2) or more customers are assigned to each open facility. (Each facility needs enough number of customers for its opening.) Then the r-gathering problem finds an r-gathering minimizing a designated cost. Armon gave a simple 3-approximation algorithm for the r-gathering problem and proved that with assumption P ≠ NP the problem cannot be approximated within a factor of less than 3 for any r ≥ 3. The running time of the 3-approximation algorithm is O(|C||F|+r|C|+|C|log|C|)). In this paper we improve the running time of the algorithm by (1) removing the sort in the algorithm and (2) designing a simple but efficient data structure.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.6 pp.1149-1151
- Publication Date
- 2016/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E99.A.1149
- Type of Manuscript
- Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Toshihiro AKAGI
Gunma University
Ryota ARAI
Gunma University
Shin-ichi NAKANO
Gunma University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Toshihiro AKAGI, Ryota ARAI, Shin-ichi NAKANO, "Faster Min-Max r-Gatherings" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 6, pp. 1149-1151, June 2016, doi: 10.1587/transfun.E99.A.1149.
Abstract: An r-gathering of customers C to facilities F is an assignment A of C to open facilities F' ⊂ F such that r (≥ 2) or more customers are assigned to each open facility. (Each facility needs enough number of customers for its opening.) Then the r-gathering problem finds an r-gathering minimizing a designated cost. Armon gave a simple 3-approximation algorithm for the r-gathering problem and proved that with assumption P ≠ NP the problem cannot be approximated within a factor of less than 3 for any r ≥ 3. The running time of the 3-approximation algorithm is O(|C||F|+r|C|+|C|log|C|)). In this paper we improve the running time of the algorithm by (1) removing the sort in the algorithm and (2) designing a simple but efficient data structure.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.1149/_p
Copy
@ARTICLE{e99-a_6_1149,
author={Toshihiro AKAGI, Ryota ARAI, Shin-ichi NAKANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Faster Min-Max r-Gatherings},
year={2016},
volume={E99-A},
number={6},
pages={1149-1151},
abstract={An r-gathering of customers C to facilities F is an assignment A of C to open facilities F' ⊂ F such that r (≥ 2) or more customers are assigned to each open facility. (Each facility needs enough number of customers for its opening.) Then the r-gathering problem finds an r-gathering minimizing a designated cost. Armon gave a simple 3-approximation algorithm for the r-gathering problem and proved that with assumption P ≠ NP the problem cannot be approximated within a factor of less than 3 for any r ≥ 3. The running time of the 3-approximation algorithm is O(|C||F|+r|C|+|C|log|C|)). In this paper we improve the running time of the algorithm by (1) removing the sort in the algorithm and (2) designing a simple but efficient data structure.},
keywords={},
doi={10.1587/transfun.E99.A.1149},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Faster Min-Max r-Gatherings
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1149
EP - 1151
AU - Toshihiro AKAGI
AU - Ryota ARAI
AU - Shin-ichi NAKANO
PY - 2016
DO - 10.1587/transfun.E99.A.1149
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2016
AB - An r-gathering of customers C to facilities F is an assignment A of C to open facilities F' ⊂ F such that r (≥ 2) or more customers are assigned to each open facility. (Each facility needs enough number of customers for its opening.) Then the r-gathering problem finds an r-gathering minimizing a designated cost. Armon gave a simple 3-approximation algorithm for the r-gathering problem and proved that with assumption P ≠ NP the problem cannot be approximated within a factor of less than 3 for any r ≥ 3. The running time of the 3-approximation algorithm is O(|C||F|+r|C|+|C|log|C|)). In this paper we improve the running time of the algorithm by (1) removing the sort in the algorithm and (2) designing a simple but efficient data structure.
ER -
English
