Speeding up pairwise comparisons for large scale ranking and Selection

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)Not applicablepeer-review

View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Title of host publication2016 Winter Simulation Conference (WSC)
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages749-757
ISBN (Print)9781509044863
StatePublished - 17 Jan 2017

Publication series

Name
ISSN (Print)0891-7736

Conference

Title2016 Winter Simulation Conference, WSC 2016
PlaceUnited States
CityWashington
Period11 - 14 December 2016

Abstract

Classical sequential ranking-And-selection (R&S) procedures require all pairwise comparisons after collecting one additional observation from each surviving system, which is typically an O(k2) operation where k is the number of systems. When the number of systems is large (e.g., millions), these comparisons can be very costly and may significantly slow down the R&S procedures. In this paper we revise KN procedure slightly and show that one may reduce the computational complexity of all pairwise comparisons to an O(k) operation, thus significantly reducing the computational burden. Numerical experiments show that the computational time reduces by orders of magnitude even for moderate numbers of systems.

Citation Format(s)

Speeding up pairwise comparisons for large scale ranking and Selection. / Hong, L. Jeff; Luo, Jun; Zhong, Ying.

2016 Winter Simulation Conference (WSC). Institute of Electrical and Electronics Engineers Inc., 2017. p. 749-757.

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)Not applicablepeer-review