Earticle

초록

영어

This paper researches the issue of the housing allocation problem(HAP), in which the agents assign optimal preference order housing if they give preference order to representative housing for n agents and m houses (n = m, n ≠ m). Traditional top trading cycle(TTC) algorithm shows that each agent chooses the best(first) preference order to home and selects the best preference house in cycle. For the remaining unassigned agents and houses, finds the cycle. In this case, unassigned agents have a worse order of preference(in the worst case, they have a worst preferred housing). To solve the this problem, this paper reverse delete from worst preference order to best. In this process, if only one cell is left in a row(agent) or column(house), this algorithm selects that preference order cell. Applying to 16 benchmarking data, the proposed algorithm allocating optimal housing for all data.

한국어

본 논문은 n명의 에이전트들이 m대의 주택 (n = m, n ≠ m)에 대해 선호순서를 부여할 경우 최적의 주택을 배정하 는 주택 배정 문제를 연구하였다. 기존의 최상 선호순서 거래 사이클 알고리즘은 각 에이전트가 최상의 선호순서(1순위) 주택을 선택하여 형성된 사이클에 주택을 배정하고, 남은 에이전트들과 미배정된 주택을 대상으로 다시 사이클을 형성하 는 방법을 적용하였다. 이 경우 미 배정된 에이전트들은 보다 좋지 않은 선호순서(최악의 경우 가장 선호하지 않는 주택 배정)의 주택을 배정받을 가능성이 있다. 이러한 문제점을 해결하기 위해 본 논문에서는 최악의 선호순서부터 역-삭제하 는 과정에서 행(에이전트) 또는 열(주택)에 1개만 남는 경우 해당 선호순서 셀을 선택하는 방법을 제안하였다. 제안된 알고리즘을 16개의 벤치마킹 데이터들에 적용한 결과 모든 데이터들에 대해 최적의 주택을 배정할 수 있음을 보였다.

목차

요약
Abstract
Ⅰ. 서론
Ⅱ. 주택 배정 문제
Ⅲ. 선호순서 역-삭제 알고리즘
Ⅳ. 적용 및 결과 분석
Ⅴ. 결론
References

키워드

저자

• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 교수 ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380