BROWSE

Related Scientist

dabeen,lee's photo.

dabeen,lee
이산수학그룹
more info

ITEM VIEW & DOWNLOAD

Test Score Algorithms for Budgeted Stochastic Utility Maximization

DC Field Value Language
dc.contributor.authorDabeen Lee-
dc.contributor.authorVojnovic, Milan-
dc.contributor.authorYun, Se-Young-
dc.date.accessioned2023-05-25T22:01:32Z-
dc.date.available2023-05-25T22:01:32Z-
dc.date.created2023-05-24-
dc.date.issued2022-08-
dc.identifier.issn2575-1484-
dc.identifier.urihttps://pr.ibs.re.kr/handle/8788114/13393-
dc.description.abstract<jats:p> Motivated by recent developments in designing algorithms based on individual item scores for solving utility maximization problems, we study the framework of using test scores, defined as a statistic of observed individual item performance data, for solving the budgeted stochastic utility maximization problem. We extend an existing scoring mechanism, namely, the replication test scores, to incorporate heterogeneous item costs as well as item values. We show that a natural greedy algorithm that selects items solely based on their replication test scores outputs solutions within a constant factor of the optimum for the class of functions satisfying an extended diminishing returns property. Our algorithms and approximation guarantees assume that test scores are noisy estimates of certain expected values with respect to marginal distributions of individual item values, thus making our algorithms practical and extending previous work that assumes noiseless estimates. Moreover, we show how our algorithm can be adapted to the setting in which items arrive in a streaming fashion while maintaining the same approximation guarantee. We present numerical results, using synthetic data and data sets from the Academia.StackExchange Q&amp;A forum, which show that our test score algorithm can achieve competitiveness and in some cases better performance than a benchmark algorithm that requires access to a value oracle to evaluate function values. </jats:p><jats:p> Funding: This research was supported, in part, by the Institute for Basic Science [Grants IBS-R029-C1, IBS-R029-Y2]. </jats:p>-
dc.titleTest Score Algorithms for Budgeted Stochastic Utility Maximization-
dc.typeArticle-
dc.type.rimsART-
dc.identifier.rimsid80833-
dc.contributor.affiliatedAuthorDabeen Lee-
dc.identifier.doi10.1287/ijoo.2022.0075-
dc.identifier.bibliographicCitationINFORMS Journal on Optimization, v.5, no.1, pp.27 - 67-
dc.relation.isPartOfINFORMS Journal on Optimization-
dc.citation.titleINFORMS Journal on Optimization-
dc.citation.volume5-
dc.citation.number1-
dc.citation.startPage27-
dc.citation.endPage67-
dc.description.journalClass1-
dc.description.journalClass1-
dc.description.isOpenAccessN-
dc.description.journalRegisteredClassother-
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse