Publications

Detailed Information

대학 입학 지원 최적화 문제 : The College Application Problem

Cited 0 time in Web of Science Cited 0 time in Scopus
Authors

카푸르 맥스

Advisor
홍성필
Issue Date
2022
Publisher
서울대학교 대학원
Keywords
submodularmaximizationknapsackproblemsapproximationalgorithms
Description
학위논문(석사) -- 서울대학교대학원 : 공과대학 산업공학과, 2022. 8. 홍성필.
Abstract
본 논문은 다수의 확률 변수로 구성된 포트폴리오의 기대 최댓값을 예산 조건 아래서 최대화하는 문제를 고려한다. 이를 대학 입학 지원 최적화 문제라고 부른다. 각 확률 변수의 비용, 즉 각 대학의 지원 비용이 동일한 경우, 최적 포트폴리오는 예산 제약식으로 결정된 포함 사슬 관계 성질을 가짐을 보이고 이를 바탕으로 다항 시간 해법을 제시한다. 대학의 지원 비용이 서로 다른 경우, 문제가 NP-complete함을 증명한다. 일반적인 문제를 위해 4가지 해법을 제시하며, 분지한계 기반 해법, 의사 다항 시간에 정확한 해를 출력하는 동적 계획 해법, 다른 동적 계획 기반으로 완전 다항 시간 근사 해법(fully polynomial-time approximation scheme), 그리고 모의 담금질(simulated annealing)을 이용한 휴리스틱 해법을 포함한다. 수리적 실험을 통해 알고리즘의 정확도와 효율성을 보인다.
This paper considers the maximization of the expected maximum value of a portfolio of random variables subject to a budget constraint. We refer to this as the optimal college application problem. When each variable's cost, or each college's application fee, is identical, we show that the optimal portfolios are nested in the budget constraint, yielding an exact polynomial-time algorithm. When colleges differ in their application fees, we show that the problem is NP-complete. We provide four algorithms for this more general setup: a branch-and-bound routine, a dynamic program that produces an exact solution in pseudopolynomial time, a different dynamic program that yields a fully polynomial-time approximation scheme, and a simulated-annealing heuristic. Numerical experiments demonstrate the algorithms' accuracy and efficiency.
Language
kor
URI
https://hdl.handle.net/10371/187651

https://dcollection.snu.ac.kr/common/orgView/000000172202
Files in This Item:
Appears in Collections:

Altmetrics

Item View & Download Count

  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Share