서브메뉴
검색
Advice-Augmented Algorithms for Online Matching and Resource Allocation
Advice-Augmented Algorithms for Online Matching and Resource Allocation
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20250211152706
- ISBN
- 9798384052920
- DDC
- 004
- 서명/저자
- Advice-Augmented Algorithms for Online Matching and Resource Allocation
- 발행사항
- [Sl] : Cornell University, 2024
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2024
- 형태사항
- 148 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 86-03, Section: B.
- 주기사항
- Advisor: Williamson, David.
- 학위논문주기
- Thesis (Ph.D.)--Cornell University, 2024.
- 초록/해제
- 요약Real life problems are full of uncertainty. How we handle it is important, since it affects the design and performance of algorithms. Often, the uncertainty is assumed to follow some known distribution, but in practice the estimate of the distribution may or may not be accurate. At other times, the uncertainty is assumed to be adversarial, but this can be too pessimistic for most real life instances. Advice-augmented algorithms aim to bridge the gap between these two models. In this framework, the algorithm is given some advice or prediction (e.g. from historical data, forecasts, or expert advice), whose quality is unknown. We aim to design algorithms that perform well when the quality is high (consistency), yet remain robust in their performance even when the quality is low (robustness).We consider advice-augmented algorithms for two problems. The first is two-stage matching: We design an algorithm that attains the optimal tradeoff between consistency and robustness. The second is Nash social welfare maximization in online resource allocation: We show that access to reasonable predictions gives an exponential improvement over the worst-case performance. Convex optimization plays a key role in both results.
- 일반주제명
- Information technology
- 키워드
- Online matching
- 기타저자
- Cornell University Operations Research and Information Engineering
- 기본자료저록
- Dissertations Abstracts International. 86-03B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008250123s2024 us c eng d■001000017163425
■00520250211152706
■006m o d
■007cr#unu||||||||
■020 ▼a9798384052920
■035 ▼a(MiAaPQ)AAI31488353
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a004
■1001 ▼aJin, Billy Zhengxu.▼0(orcid)0000-0002-6362-2048
■24510▼aAdvice-Augmented Algorithms for Online Matching and Resource Allocation
■260 ▼a[Sl]▼bCornell University▼c2024
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2024
■300 ▼a148 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 86-03, Section: B.
■500 ▼aAdvisor: Williamson, David.
■5021 ▼aThesis (Ph.D.)--Cornell University, 2024.
■520 ▼aReal life problems are full of uncertainty. How we handle it is important, since it affects the design and performance of algorithms. Often, the uncertainty is assumed to follow some known distribution, but in practice the estimate of the distribution may or may not be accurate. At other times, the uncertainty is assumed to be adversarial, but this can be too pessimistic for most real life instances. Advice-augmented algorithms aim to bridge the gap between these two models. In this framework, the algorithm is given some advice or prediction (e.g. from historical data, forecasts, or expert advice), whose quality is unknown. We aim to design algorithms that perform well when the quality is high (consistency), yet remain robust in their performance even when the quality is low (robustness).We consider advice-augmented algorithms for two problems. The first is two-stage matching: We design an algorithm that attains the optimal tradeoff between consistency and robustness. The second is Nash social welfare maximization in online resource allocation: We show that access to reasonable predictions gives an exponential improvement over the worst-case performance. Convex optimization plays a key role in both results.
■590 ▼aSchool code: 0058.
■650 4▼aInformation technology
■653 ▼aResource allocation
■653 ▼aOnline matching
■690 ▼a0796
■690 ▼a0489
■71020▼aCornell University▼bOperations Research and Information Engineering.
■7730 ▼tDissertations Abstracts International▼g86-03B.
■790 ▼a0058
■791 ▼aPh.D.
■792 ▼a2024
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17163425▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
