지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers Journal of KIISE Journal of KIISE Vol.48 No.4
- 발행연도
- 2021.4
- 수록면
- 377 - 390 (14page)
- DOI
- 10.5626/JOK.2021.48.4.377
이용수
초록· 키워드
오류제보하기
본 논문에서는 용량 제약이 있는 설비 배치 문제(CFL)에 대한 근사 알고리즘을 실용적으로 변형한 새로운 휴리스틱과 이것이 이용하는 선형계획법 완화를 실험적으로 평가·분석한다. CFL은 컴퓨터과학 및 운용과학 분야에서 널리 연구되어온 문제이나, 선형계획법에 기반한 상수 인자 근사 알고리즘은 최근에야 발견되었다. 그러나, 기존의 느슨한 분석으로는 해당 선형계획법 완화의 정수격차(integrality gap)를 288로 상한할 수 있을 뿐이었다. 본 논문은 실제 데이터셋에서의 근사율과 정수격차를 측정함으로써, 휴리스틱 및 여기에 사용된 선형계획의 실질적인 성능을 평가함과 동시에 이론적인 추측을 위한 근거를 마련하고자 한다. 기존의 근사 알고리즘은 이론적인 것이어서 실제로 구현하기에는 지나치게 느린 수행시간을 갖는다. 본 논문에서는 수치적 안정성을 해치지 않으면서도 수행시간을 개선할 수 있는 휴리스틱들을 제안하고 알고리즘의 파라미터를 실험적으로 최적화하여 고속의 구현을 얻는다.
목차
요약
Abstract
1. 서론
2. 문제의 정의 및 기존 알고리즘
3. 구현 방법론
4. 파라미터 조정
5. 계산적 분석
6. 결론 및 향후 연구
References
참고문헌 (16)
참고문헌 신청
M. R. Korupolu, C. G. Plaxton, and R. Rajaraman, "Analysis of a local search heuristic for facility location problems," Journal of Algorithms, Vol. 37, No. 1, pp. 146-188, 2000.
M. Bansal, N. Garg, and N. Gupta, "A 5-approximation for capacitated facility location," Proc. of the European Symposium on Algorithms (ESA), pp. 133-144, 2012.
H.-C. An, M. Singh, and O. Svensson, "LP-based algorithms for capacitated facility location," SIAM Journal of Computing, Vol. 46, No. 1, pp. 272-306, 2017.
A. A. Kuehn and M. J. Hamburger, "A heuristic program for locating warehouses," Management Science, Vol. 9, No. 4, pp. 643-666, 1963.
D. B. Shmoys, E. Tardos, and K. Aardal, "Approximation algorithms for facility location problems (extended abstract)," Proc. of the Annual ACM Symposium on Theory of Computing (STOC), pp. 265-274, 1997.
M. Bansal, N. Garg, and N. Gupta, "A 5-approximation for capacitated facility location," Proc. of the European Symposium on Algorithms (ESA), pp. 133-144, 2012.
H.-C. An, M. Singh, and O. Svensson, "LP-based algorithms for capacitated facility location," SIAM Journal of Computing, Vol. 46, No. 1, pp. 272-306, 2017.
A. A. Kuehn and M. J. Hamburger, "A heuristic program for locating warehouses," Management Science, Vol. 9, No. 4, pp. 643-666, 1963.
D. B. Shmoys, E. Tardos, and K. Aardal, "Approximation algorithms for facility location problems (extended abstract)," Proc. of the Annual ACM Symposium on Theory of Computing (STOC), pp. 265-274, 1997.
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
용량 제약이 있는 설비 위치 선정 문제에 대한 근사 알고리즘 및 선형계획법 완화의 계산적 분석
한국정보과학회 학술발표논문집
2018 .06
-
Efficient and Robust Implementation of the Algorithms for Parity-Constrained k-Center and Facility Location
Journal of KIISE
2021 .03
-
효율적인 계획 수립을 위한 동작-기반의 휴리스틱
한국산학기술학회 논문지
2015 .09
-
개척자 기반 새로운 최적화 알고리즘: POA (Pioneer-inspired Optimization Algorithm)
한국지능시스템학회 논문지
2021 .12
-
기초프로그래밍 교육을 위한 언어 CFL의 설계, 구현 및 적용
한국정보과학회 학술발표논문집
2016 .06
-
가상 네트워크 대응 휴리스틱 알고리즘에서 지역 최적값의 의미
한국통신학회 학술대회논문집
2016 .11
-
단일 호이스트 생산시스템에서 다양한 주문을 처리하기 위한 분지한계 기반의 휴리스틱 일정계획
대한산업공학회지
2016 .06
-
A* 탐색의 속도 향상을 위한 근사 휴리스틱 비용 계산
제어로봇시스템학회 각 지부별 자료집
2015 .12
-
휴리스틱 그래프 탐색 기법에 의한 충돌회피 경로계획 방법
대한전기학회 학술대회 논문집
2018 .07
-
휴리스틱 파지 알고리즘을 활용한 자율형 재활용 로봇 시스템
한국정보과학회 학술발표논문집
2023 .06
-
부분 선형 근사 기법을 이용한 정적 무장 할당 연구
한국항공우주학회 학술발표회 초록집
2016 .11
-
가상경계기법을 활용한 얇은 물체 주위 유동의 해석결과에 높은 CFL수가 미치는 영향
한국전산유체공학회 학술대회논문집
2021 .05
-
이기종 설비에서 독립 작업의 휴리스틱 일정계획 비교 연구
대한산업공학회 추계학술대회 논문집
2022 .11
-
구간별 선형 근사를 통한 On-device 용 화자 인식 모델 최적화
한국통신학회 학술대회논문집
2025 .02
-
Integrity Heuristic as Tie-Breaking for Classical Task Planning
제어로봇시스템학회 국제학술대회 논문집
2023 .10
-
휴리스틱 방법을 이용한 카메라 외부표정요소 추정
한국측량학회 학술대회자료집
2017 .04
-
휴리스틱 모형 기반 사고 취약시설 안전성능함수 개발
대한교통학회 학술대회지
2020 .10
-
An Algorithm for the Robust Single Source Capacitated Facility Location Problem Under Demand Uncertainty
대한산업공학회 춘계공동학술대회 논문집
2017 .04
-
공학해석용 최적 격자 생성을 위한 휴리스틱 방안
대한산업공학회 추계학술대회 논문집
2017 .11
-
메타 휴리스틱 알고리즘을 이용한 우주비행체 랑데부 궤적 최적화
한국항공우주학회 학술발표회 초록집
2023 .04
이 논문의 저자 정보
이 논문과 함께 이용한 논문
Efficient and Robust Implementation of the Algorithms for Parity-Constrained k-Center and Facility Location
김강산
,
안형찬
Journal of KIISE
2021
.03
객체인식을활용한 3D 점유 격자 지도기반복셀 매핑 연구
최영은
,
신수용
한국통신학회 학술대회논문집
2024
.11
A Novel Heuristic Algorithm for Online 3D Bin Packing
Thanh-Hung Nguyen
,
Viet-Thang T
,
an
외 2명
제어로봇시스템학회 국제학술대회 논문집
2021
.10
점유 복셀지도를 이용한 동적환경 대상 구조 도면 작성 방법
이유철
,
유원필
제어로봇시스템학회 국내학술대회 논문집
2021
.06
도로매칭 알고리즘 성능 향상에 관한 연구
양인철
,
전우훈
디지털콘텐츠학회논문지
2020
.01
최근 본 자료
댓글(0)
0