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
본 논문에서는 최근에 제안된 변형을 연구합니다. r-집결 문제. 안 r-모임 고객 C 시설로 F 과제다 A of C 에 개방형 시설 F' ⊂ F 그렇게 r 각 개방형 시설에는 이상의 고객이 배정됩니다. (각 시설은 개점을 위해 충분한 수의 고객이 필요합니다.) 개점 비용을 감안할 때 op(f) 각각 f∈F및 연결 비용 co(c,f) 각 쌍에 대해 c∈C 및 f∈F, 비용 r-모임 A 최대입니다{최대c∈C{co(c, A(c))}, 최대f∈F'{op(f)}}. 그만큼 r-수집 문제 찾는 것으로 구성됩니다. r- 최소한의 비용으로 모임을 갖는다. 가정 F 비상 대피소를 위한 장소 세트입니다. op(f)은 대피소를 준비하는 데 필요한 시간입니다. f∈F및 co(c,f)는 사람에게 필요한 시간이다 c∈C 지정된 대피소에 도달하기 위해 f=A(c)∈F. 그런 다음 r-모임은 각각의 개방형 대피소가 제공되는 대피 계획에 해당합니다. r 또는 더 많은 사람과 r-수집문제는 대피시간을 최소화하는 대피계획을 찾는 것으로 구성된다. 그러나 위의 솔루션에서는 더 가까운 개방형 대피소가 있음에도 불구하고 일부 사람이 더 멀리 개방된 대피소에 배정될 수 있습니다. 긴급 상황에서는 그러한 임무를 받아들이기가 어려울 수 있습니다. 따라서 Armon은 문제에 대해 하나의 추가 제약 조건, 즉 각 고객을 가장 가까운 개방형 시설에 할당해야 한다는 점을 고려하고 문제에 대해 9-근사 다항식 시간 알고리즘을 제공했습니다. 우리는 문제에 대한 간단한 3-근사 알고리즘을 설계했습니다. 운행시간은 O(r|C||F|).
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.
부
Shin-ichi NAKANO, "Assigning Proximity Facilities for Gatherings" in IEICE TRANSACTIONS on Information,
vol. E107-D, no. 3, pp. 383-385, March 2024, doi: 10.1587/transinf.2023EDP7181.
Abstract: In this paper we study a recently proposed variant of the r-gathering problem. An r-gathering of customers C to facilities F is an assignment A of C to open facilities F' ⊂ F such that r or more customers are assigned to each open facility. (Each facility needs enough number of customers to open.) Given an opening cost op(f) for each f∈F, and a connecting cost co(c,f) for each pair of c∈C and f∈F, the cost of an r-gathering A is max{maxc∈C{co(c, A(c))}, maxf∈F'{op(f)}}. The r-gathering problem consists of finding an r-gathering having the minimum cost. Assume that F is a set of locations for emergency shelters, op(f) is the time needed to prepare a shelter f∈F, and co(c,f) is the time needed for a person c∈C to reach assigned shelter f=A(c)∈F. Then an r-gathering corresponds to an evacuation plan such that each open shelter serves r or more people, and the r-gathering problem consists of finding an evacuation plan minimizing the evacuation time span. However in a solution above some person may be assigned to a farther open shelter although it has a closer open shelter. It may be difficult for the person to accept such an assignment for an emergency situation. Therefore, Armon considered the problem with one more additional constraint, that is, each customer should be assigned to a closest open facility, and gave a 9-approximation polynomial-time algorithm for the problem. We have designed a simple 3-approximation algorithm for the problem. The running time is O(r|C||F|).
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2023EDP7181/_p
부
@ARTICLE{e107-d_3_383,
author={Shin-ichi NAKANO, },
journal={IEICE TRANSACTIONS on Information},
title={Assigning Proximity Facilities for Gatherings},
year={2024},
volume={E107-D},
number={3},
pages={383-385},
abstract={In this paper we study a recently proposed variant of the r-gathering problem. An r-gathering of customers C to facilities F is an assignment A of C to open facilities F' ⊂ F such that r or more customers are assigned to each open facility. (Each facility needs enough number of customers to open.) Given an opening cost op(f) for each f∈F, and a connecting cost co(c,f) for each pair of c∈C and f∈F, the cost of an r-gathering A is max{maxc∈C{co(c, A(c))}, maxf∈F'{op(f)}}. The r-gathering problem consists of finding an r-gathering having the minimum cost. Assume that F is a set of locations for emergency shelters, op(f) is the time needed to prepare a shelter f∈F, and co(c,f) is the time needed for a person c∈C to reach assigned shelter f=A(c)∈F. Then an r-gathering corresponds to an evacuation plan such that each open shelter serves r or more people, and the r-gathering problem consists of finding an evacuation plan minimizing the evacuation time span. However in a solution above some person may be assigned to a farther open shelter although it has a closer open shelter. It may be difficult for the person to accept such an assignment for an emergency situation. Therefore, Armon considered the problem with one more additional constraint, that is, each customer should be assigned to a closest open facility, and gave a 9-approximation polynomial-time algorithm for the problem. We have designed a simple 3-approximation algorithm for the problem. The running time is O(r|C||F|).},
keywords={},
doi={10.1587/transinf.2023EDP7181},
ISSN={1745-1361},
month={March},}
부
TY - JOUR
TI - Assigning Proximity Facilities for Gatherings
T2 - IEICE TRANSACTIONS on Information
SP - 383
EP - 385
AU - Shin-ichi NAKANO
PY - 2024
DO - 10.1587/transinf.2023EDP7181
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E107-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2024
AB - In this paper we study a recently proposed variant of the r-gathering problem. An r-gathering of customers C to facilities F is an assignment A of C to open facilities F' ⊂ F such that r or more customers are assigned to each open facility. (Each facility needs enough number of customers to open.) Given an opening cost op(f) for each f∈F, and a connecting cost co(c,f) for each pair of c∈C and f∈F, the cost of an r-gathering A is max{maxc∈C{co(c, A(c))}, maxf∈F'{op(f)}}. The r-gathering problem consists of finding an r-gathering having the minimum cost. Assume that F is a set of locations for emergency shelters, op(f) is the time needed to prepare a shelter f∈F, and co(c,f) is the time needed for a person c∈C to reach assigned shelter f=A(c)∈F. Then an r-gathering corresponds to an evacuation plan such that each open shelter serves r or more people, and the r-gathering problem consists of finding an evacuation plan minimizing the evacuation time span. However in a solution above some person may be assigned to a farther open shelter although it has a closer open shelter. It may be difficult for the person to accept such an assignment for an emergency situation. Therefore, Armon considered the problem with one more additional constraint, that is, each customer should be assigned to a closest open facility, and gave a 9-approximation polynomial-time algorithm for the problem. We have designed a simple 3-approximation algorithm for the problem. The running time is O(r|C||F|).
ER -