Coupled bisection for root ordering

被引：0

作者：

Pallone, Stephen N. ^{[1
]}

Frazier, Peter I. ^{[1
]}

Henderson, Shane G. ^{[1
]}

机构：

[1] Cornell Univ, Sch Operat Res & Informat Engn, Ithaca, NY 14853 USA

来源：

OPERATIONS RESEARCH LETTERS | 2016年 / 44卷 / 02期

关键词：

Bisection; Dynamic programming; Lagrangian relaxation; Index policies; INDEX;

D O I：

10.1016/j.orl.2015.12.015

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the problem of solving multiple "coupled" root-finding problems at once, in that we can evaluate every function at the same point simultaneously. Using a dynamic programming formulation, we show that a sequential bisection algorithm is a close-to-optimal method for finding a ranking with respect to the zeros of these functions. We show the ranking can be found in linear time, prove an asymptotic approximation guarantee of 1.44, and conjecture that this policy is near-optimal. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：165 / 169

页数：5

共 13 条

[1]

Castro R, 2008, SIGNALS COMMUN TECHN, P177, DOI 10.1007/978-0-387-49819-5_8

[2] Index policies for discounted bandit problems with availability constraints [J].

Dayanik, Savas ;

Powell, Warren ;

Yamazaki, Kazutoshi .

ADVANCES IN APPLIED PROBABILITY, 2008, 40 (02) :377-400

[3]

Gittins J., PROGR STAT, V2

[4] Index Policies for the Admission Control and Routing of Impatient Customers to Heterogeneous Service Stations [J].

Glazebrook, K. D. ;

Kirkbride, C. ;

Ouenniche, J. .

OPERATIONS RESEARCH, 2009, 57 (04) :975-989

[5]

Hu WC, 2014, WINT SIMUL C PROC, P3904, DOI 10.1109/WSC.2014.7020216

[6] Computing a Classic Index for Finite-Horizon Bandits [J].

Nino-Mora, Jose .

INFORMS JOURNAL ON COMPUTING, 2011, 23 (02) :254-267

[7]

SCHWEDER T, 1982, SCAND J STAT, V9, P165

[8]

SHAKED M, 1980, J ROY STAT SOC B MET, V42, P192

[9]

Shaked M, 2007, SPRINGER SER STAT, P3

[10] Lead-free piezoelectric ceramics: Alternatives for PZT? [J].

Shrout T.R. ;

Zhang S.J. .

Journal of Electroceramics, 2007, 19 (1) :111-124

← 1 2 →