검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

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

Assigning Proximity Facilities for Gatherings 모임을 위한 근접 시설 지정

Shin-ichi NAKANO

  • 조회수

    1

  • 이것을 인용

요약 :

본 논문에서는 최근에 제안된 변형을 연구합니다. r-집결 문제. 안 r-모임 고객 C 시설로 F 과제다 A of C개방형 시설 F'F 그렇게 r 각 개방형 시설에는 이상의 고객이 배정됩니다. (각 시설은 개점을 위해 충분한 수의 고객이 필요합니다.) 개점 비용을 감안할 때 op(f) 각각 fF및 연결 비용 co(c,f) 각 쌍에 대해 cCfF, 비용 r-모임 A 최대입니다{최대cC{co(c, A(c))}, 최대fF'{op(f)}}. 그만큼 r-수집 문제 찾는 것으로 구성됩니다. r- 최소한의 비용으로 모임을 갖는다. 가정 F 비상 대피소를 위한 장소 세트입니다. op(f)은 대피소를 준비하는 데 필요한 시간입니다. fFco(c,f)는 사람에게 필요한 시간이다 cC 지정된 대피소에 도달하기 위해 f=A(c)∈F. 그런 다음 r-모임은 각각의 개방형 대피소가 제공되는 대피 계획에 해당합니다. r 또는 더 많은 사람과 r-수집문제는 대피시간을 최소화하는 대피계획을 찾는 것으로 구성된다. 그러나 위의 솔루션에서는 더 가까운 개방형 대피소가 있음에도 불구하고 일부 사람이 더 멀리 개방된 대피소에 배정될 수 있습니다. 긴급 상황에서는 그러한 임무를 받아들이기가 어려울 수 있습니다. 따라서 Armon은 문제에 대해 하나의 추가 제약 조건, 즉 각 고객을 가장 가까운 개방형 시설에 할당해야 한다는 점을 고려하고 문제에 대해 9-근사 다항식 시간 알고리즘을 제공했습니다. 우리는 문제에 대한 간단한 3-근사 알고리즘을 설계했습니다. 운행시간은 O(r|C||F|).

발행
IEICE TRANSACTIONS on Information Vol.E107-D No.3 pp.383-385
발행일
2024/03/01
공개일
2023/11/27
온라인 ISSN
1745-1361
DOI
10.1587/transinf.2023EDP7181
원고의 종류
PAPER
범주
정보시스템의 기초

작성자

Shin-ichi NAKANO
  Gunma University

키워드