Speeding up pairwise comparisons for large scale ranking and Selection

L. Jeff Hong; Jun Luo; Ying Zhong

doi:10.1109/WSC.2016.7822138

Speeding up pairwise comparisons for large scale ranking and Selection

L. Jeff Hong, Jun Luo, Ying Zhong

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Scopus citations

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.

Original language	English (US)
Title of host publication	2016 Winter Simulation Conference
Subtitle of host publication	Simulating Complex Service Systems, WSC 2016
Editors	Theresa M. Roeder, Peter I. Frazier, Robert Szechtman, Enlu Zhou
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	749-757
Number of pages	9
ISBN (Electronic)	9781509044863
DOIs	https://doi.org/10.1109/WSC.2016.7822138
State	Published - Jul 2 2016
Externally published	Yes
Event	2016 Winter Simulation Conference, WSC 2016 - Arlington, United States Duration: Dec 11 2016 → Dec 14 2016

Publication series

Name	Proceedings - Winter Simulation Conference
Volume	0
ISSN (Print)	0891-7736

Conference

Conference	2016 Winter Simulation Conference, WSC 2016
Country/Territory	United States
City	Arlington
Period	12/11/16 → 12/14/16

Bibliographical note

Publisher Copyright:
© 2016 IEEE.

Publisher link

10.1109/WSC.2016.7822138

Find It

Find It at U of M Libraries

Cite this

Hong, L. J., Luo, J., & Zhong, Y. (2016). Speeding up pairwise comparisons for large scale ranking and Selection. In T. M. Roeder, P. I. Frazier, R. Szechtman, & E. Zhou (Eds.), 2016 Winter Simulation Conference: Simulating Complex Service Systems, WSC 2016 (pp. 749-757). Article 7822138 (Proceedings - Winter Simulation Conference; Vol. 0). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/WSC.2016.7822138

Speeding up pairwise comparisons for large scale ranking and Selection. / Hong, L. Jeff; Luo, Jun; Zhong, Ying.
2016 Winter Simulation Conference: Simulating Complex Service Systems, WSC 2016. ed. / Theresa M. Roeder; Peter I. Frazier; Robert Szechtman; Enlu Zhou. Institute of Electrical and Electronics Engineers Inc., 2016. p. 749-757 7822138 (Proceedings - Winter Simulation Conference; Vol. 0).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Hong, LJ, Luo, J & Zhong, Y 2016, Speeding up pairwise comparisons for large scale ranking and Selection. in TM Roeder, PI Frazier, R Szechtman & E Zhou (eds), 2016 Winter Simulation Conference: Simulating Complex Service Systems, WSC 2016., 7822138, Proceedings - Winter Simulation Conference, vol. 0, Institute of Electrical and Electronics Engineers Inc., pp. 749-757, 2016 Winter Simulation Conference, WSC 2016, Arlington, United States, 12/11/16. https://doi.org/10.1109/WSC.2016.7822138

Hong LJ, Luo J, Zhong Y. Speeding up pairwise comparisons for large scale ranking and Selection. In Roeder TM, Frazier PI, Szechtman R, Zhou E, editors, 2016 Winter Simulation Conference: Simulating Complex Service Systems, WSC 2016. Institute of Electrical and Electronics Engineers Inc. 2016. p. 749-757. 7822138. (Proceedings - Winter Simulation Conference). doi: 10.1109/WSC.2016.7822138

Hong, L. Jeff ; Luo, Jun ; Zhong, Ying. / Speeding up pairwise comparisons for large scale ranking and Selection. 2016 Winter Simulation Conference: Simulating Complex Service Systems, WSC 2016. editor / Theresa M. Roeder ; Peter I. Frazier ; Robert Szechtman ; Enlu Zhou. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 749-757 (Proceedings - Winter Simulation Conference).

@inproceedings{d671f595f19e4e34b45edab16c2bf7f5,

title = "Speeding up pairwise comparisons for large scale ranking and Selection",

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.",

author = "Hong, {L. Jeff} and Jun Luo and Ying Zhong",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 2016 Winter Simulation Conference, WSC 2016 ; Conference date: 11-12-2016 Through 14-12-2016",

year = "2016",

month = jul,

day = "2",

doi = "10.1109/WSC.2016.7822138",

language = "English (US)",

series = "Proceedings - Winter Simulation Conference",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "749--757",

editor = "Roeder, {Theresa M.} and Frazier, {Peter I.} and Robert Szechtman and Enlu Zhou",

booktitle = "2016 Winter Simulation Conference",

}

TY - GEN

T1 - Speeding up pairwise comparisons for large scale ranking and Selection

AU - Hong, L. Jeff

AU - Luo, Jun

AU - Zhong, Ying

PY - 2016/7/2

Y1 - 2016/7/2

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85014170601&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85014170601&partnerID=8YFLogxK

U2 - 10.1109/WSC.2016.7822138

DO - 10.1109/WSC.2016.7822138

M3 - Conference contribution

AN - SCOPUS:85014170601

T3 - Proceedings - Winter Simulation Conference

SP - 749

EP - 757

BT - 2016 Winter Simulation Conference

A2 - Roeder, Theresa M.

A2 - Frazier, Peter I.

A2 - Szechtman, Robert

A2 - Zhou, Enlu

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 Winter Simulation Conference, WSC 2016

Y2 - 11 December 2016 through 14 December 2016

ER -

Speeding up pairwise comparisons for large scale ranking and Selection

Abstract

Publication series

Conference

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this