Query minimization under stochastic uncertainty

Steven Chaplick; Magnús M. Halldórsson; Murilo S. de Lima; Tigran Tonoyan

doi:10.1016/j.tcs.2021.09.032

Query minimization under stochastic uncertainty

Steven Chaplick, Magnús M. Halldórsson, Murilo S. de Lima^*, Tigran Tonoyan

^*Corresponding author for this work

Department of Computer Science

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

We study problems with stochastic uncertainty information on intervals for which the precise value can be queried by paying a cost. The goal is to devise an adaptive decision tree to find a correct solution to the problem in consideration while minimizing the expected total query cost. We show that, for the sorting problem, such a decision tree can be found in polynomial time. For the problem of finding the data item with minimum value, we have some evidence for hardness. This contradicts intuition, since the minimum problem is easier both in the online setting with adversarial inputs and in the offline verification setting. However, the stochastic assumption can be leveraged to beat both deterministic and randomized approximation lower bounds for the online setting.

Original language	English
Pages (from-to)	75-95
Number of pages	21
Journal	Theoretical Computer Science
Volume	895
DOIs	https://doi.org/10.1016/j.tcs.2021.09.032
Publication status	Published - 4 Dec 2021

Bibliographical note

Funding Information:
Partially supported by Icelandic Research Fund grant 174484-051 and by EPSRC grant EP/S033483/1 . A preliminary version of this paper appeared in volume 12118 of LNCS (LATIN 2020), pp. 181–193, 2020. https://doi.org/10.1007/978-3-030-61792-9_15 . This work started while M. S. de Lima and T. Tonoyan were at Reykjavik University, during a research visit by S. Chaplick. Part of the work was developed while M. S. de Lima was at the School of Informatics, University of Leicester, United Kingdom.

Funding Information:
Partially supported by Icelandic Research Fund grant 174484-051 and by EPSRC grant EP/S033483/1. A preliminary version of this paper appeared in volume 12118 of LNCS (LATIN 2020), pp. 181–193, 2020. https://doi.org/10.1007/978-3-030-61792-9_15. This work started while M. S. de Lima and T. Tonoyan were at Reykjavik University, during a research visit by S. Chaplick. Part of the work was developed while M. S. de Lima was at the School of Informatics, University of Leicester, United Kingdom.

Publisher Copyright:
© 2021 Elsevier B.V.

Other keywords

Online algorithms
Query minimization
Selection
Sorting
Stochastic optimization

Access to Document

10.1016/j.tcs.2021.09.032

Cite this

@article{b33f7b8c52af46ad9ed68ddf3edf3d05,

title = "Query minimization under stochastic uncertainty",

abstract = "We study problems with stochastic uncertainty information on intervals for which the precise value can be queried by paying a cost. The goal is to devise an adaptive decision tree to find a correct solution to the problem in consideration while minimizing the expected total query cost. We show that, for the sorting problem, such a decision tree can be found in polynomial time. For the problem of finding the data item with minimum value, we have some evidence for hardness. This contradicts intuition, since the minimum problem is easier both in the online setting with adversarial inputs and in the offline verification setting. However, the stochastic assumption can be leveraged to beat both deterministic and randomized approximation lower bounds for the online setting.",

keywords = "Online algorithms, Query minimization, Selection, Sorting, Stochastic optimization",

author = "Steven Chaplick and Halld{\'o}rsson, {Magn{\'u}s M.} and {de Lima}, {Murilo S.} and Tigran Tonoyan",

note = "Funding Information: Partially supported by Icelandic Research Fund grant 174484-051 and by EPSRC grant EP/S033483/1 . A preliminary version of this paper appeared in volume 12118 of LNCS (LATIN 2020), pp. 181–193, 2020. https://doi.org/10.1007/978-3-030-61792-9_15 . This work started while M. S. de Lima and T. Tonoyan were at Reykjavik University, during a research visit by S. Chaplick. Part of the work was developed while M. S. de Lima was at the School of Informatics, University of Leicester, United Kingdom. Funding Information: Partially supported by Icelandic Research Fund grant 174484-051 and by EPSRC grant EP/S033483/1. A preliminary version of this paper appeared in volume 12118 of LNCS (LATIN 2020), pp. 181–193, 2020. https://doi.org/10.1007/978-3-030-61792-9_15. This work started while M. S. de Lima and T. Tonoyan were at Reykjavik University, during a research visit by S. Chaplick. Part of the work was developed while M. S. de Lima was at the School of Informatics, University of Leicester, United Kingdom. Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2021",

month = dec,

day = "4",

doi = "10.1016/j.tcs.2021.09.032",

language = "English",

volume = "895",

pages = "75--95",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Query minimization under stochastic uncertainty

AU - Chaplick, Steven

AU - Halldórsson, Magnús M.

AU - de Lima, Murilo S.

AU - Tonoyan, Tigran

N1 - Funding Information: Partially supported by Icelandic Research Fund grant 174484-051 and by EPSRC grant EP/S033483/1 . A preliminary version of this paper appeared in volume 12118 of LNCS (LATIN 2020), pp. 181–193, 2020. https://doi.org/10.1007/978-3-030-61792-9_15 . This work started while M. S. de Lima and T. Tonoyan were at Reykjavik University, during a research visit by S. Chaplick. Part of the work was developed while M. S. de Lima was at the School of Informatics, University of Leicester, United Kingdom. Funding Information: Partially supported by Icelandic Research Fund grant 174484-051 and by EPSRC grant EP/S033483/1. A preliminary version of this paper appeared in volume 12118 of LNCS (LATIN 2020), pp. 181–193, 2020. https://doi.org/10.1007/978-3-030-61792-9_15. This work started while M. S. de Lima and T. Tonoyan were at Reykjavik University, during a research visit by S. Chaplick. Part of the work was developed while M. S. de Lima was at the School of Informatics, University of Leicester, United Kingdom. Publisher Copyright: © 2021 Elsevier B.V.

PY - 2021/12/4

Y1 - 2021/12/4

N2 - We study problems with stochastic uncertainty information on intervals for which the precise value can be queried by paying a cost. The goal is to devise an adaptive decision tree to find a correct solution to the problem in consideration while minimizing the expected total query cost. We show that, for the sorting problem, such a decision tree can be found in polynomial time. For the problem of finding the data item with minimum value, we have some evidence for hardness. This contradicts intuition, since the minimum problem is easier both in the online setting with adversarial inputs and in the offline verification setting. However, the stochastic assumption can be leveraged to beat both deterministic and randomized approximation lower bounds for the online setting.

AB - We study problems with stochastic uncertainty information on intervals for which the precise value can be queried by paying a cost. The goal is to devise an adaptive decision tree to find a correct solution to the problem in consideration while minimizing the expected total query cost. We show that, for the sorting problem, such a decision tree can be found in polynomial time. For the problem of finding the data item with minimum value, we have some evidence for hardness. This contradicts intuition, since the minimum problem is easier both in the online setting with adversarial inputs and in the offline verification setting. However, the stochastic assumption can be leveraged to beat both deterministic and randomized approximation lower bounds for the online setting.

KW - Online algorithms

KW - Query minimization

KW - Selection

KW - Sorting

KW - Stochastic optimization

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

U2 - 10.1016/j.tcs.2021.09.032

DO - 10.1016/j.tcs.2021.09.032

M3 - Article

AN - SCOPUS:85116291584

SN - 0304-3975

VL - 895

SP - 75

EP - 95

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Query minimization under stochastic uncertainty

Abstract

Bibliographical note

Other keywords

Access to Document

Fingerprint

Cite this