Operations research applications of dichotomous search

被引：7

作者：

Hassin, Refael ^{[1
]}

Sarid, Anna ^{[1
]}

机构：

[1] Tel Aviv Univ, Dept Stat & Operat Res, IL-69978 Tel Aviv, Israel

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2018年 / 265卷 / 03期

关键词：

Combinatorial optimization; Dichotomous search; Alphabetic trees; OFF-LINE INSPECTION; ALPHABETIC BINARY-TREES; ECONOMIC OPTIMIZATION; MINIMAX TREES; DIRECTIONAL INFORMATION; NONUNIFORM COSTS; DISCRETE SEARCH; FIBONACCI TREES; PROCESS SUBJECT; PREFIX CODE;

D O I：

10.1016/j.ejor.2017.07.031

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

An object is searched for in {1, ... ,N}. Queries for the object are sequentially conducted. A query at x reveals whether the object's location is greater than x. The objective is to find the object within a minimal expected number of queries. This problem is called the "dichotomous search" problem and has many versions. This paper surveys dichotomous search problems with the emphasis on Operations Research applications. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：795 / 812

页数：18

共 182 条

[31] Query strategies for priced information
Charikar, M
Fagin, R
Guruswami, V
Kleinberg, J
Raghavan, P
Sahai, A
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2002, 64 (04) : 785 - 819
[32] Chelbi A, 2009, HANDBOOK OF MAINTENANCE MANAGEMENT AND ENGINEERING, P303, DOI 10.1007/978-1-84882-472-0_13
[33] Chen Z., 2017, QUALITY ENG
[34] Lopsided trees, I: Analyses
Choi, V
Golin, MJ
[J]. ALGORITHMICA, 2001, 31 (03) : 240 - 290
[35] Choy D. M., 1977, BIT (Nordisk Tidskrift for Informationsbehandling), V17, P1, DOI 10.1007/BF01932395
[36] CONSTRUCTION OF OPTIMAL ALPHA-BETA-LEAF TREES WITH APPLICATIONS TO PREFIX CODE AND INFORMATION-RETRIEVAL
CHOY, DM
WONG, CK
[J]. SIAM JOURNAL ON COMPUTING, 1983, 12 (03) : 426 - 446
[37] OPTIMAL ALPHA-BETA TREES WITH CAPACITY CONSTRAINT
CHOY, DM
WONG, CK
[J]. ACTA INFORMATICA, 1978, 10 (03) : 273 - 296
[38] AN EXTENDED RESULT OF KLEITMAN AND SAKS CONCERNING BINARY-TREES
CHU, YC
[J]. DISCRETE APPLIED MATHEMATICS, 1985, 10 (03) : 255 - 259
[39] Economic optimization of off-line inspection procedures with inspection errors
Chun, Young H.
[J]. JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2008, 59 (06) : 863 - 865
[40] Bayesian inspection model for the production process subject to a random failure
Chun, Young H.
[J]. IIE TRANSACTIONS, 2010, 42 (04) : 304 - 316

← 1 2 3 4 5 6 7 8 9 10 →