Fetching the paper…
Reading the bibliography…
The Pandora's Box problem and its extensions capture optimization problems with stochastic input where the algorithm can obtain instantiations of input random variables at some cost.
Optimal Search for the Best Alternative
Martin L Weitzman · 1979
Earlier work this paper cites.
The ellipsoid method and its consequences in combinatorial optimization
Martin Grötschel, László Lovász, and Alexander Schrijver · 1981
Earlier work this paper cites.
Self-adjusting binary search trees
Daniel Dominic Sleator and Robert Endre Tarjan · 1985
Earlier work this paper cites.
Competitive randomized algorithms for non-uniform problems
Anna R. Karlin, Mark S. Manasse, Lyle A. McGeoch, and Susan S. Owicki · 1990
Earlier work this paper cites.
Query strategies for priced information (extended abstract)
Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, and Amit Sahai · 2000
Earlier work this paper cites.
Sorting and selection with structured costs
Anupam Gupta and Amit Kumar · 2001
Earlier work this paper cites.
Approximating min-sum set cover
Uriel Feige, László Lovász, and Prasad Tetali · 2002
Earlier work this paper cites.
Self-improving algorithms
Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu · 2006
Earlier work this paper cites.
Asking the right questions: model-driven optimization using probes
Ashish Goel, Sudipto Guha, and Kamesh Munagala · 2006
Earlier work this paper cites.
Dynamic optimality—almost
Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Patrascu · 2007
Earlier work this paper cites.
Optimal mechanism design and money burning
Jason D. Hartline and Tim Roughgarden · 2008
Earlier work this paper cites.
Multiple intents re-ranking
Yossi Azar, Iftah Gamzu, and Xiaoxin Yin · 2009
Earlier work this paper cites.
A constant factor approximation algorithm for generalized min-sum set cover
Nikhil Bansal, Anupam Gupta, and Ravishankar Krishnaswamy · 2010
Earlier work this paper cites.
Self-improving algorithms for convex hulls
Kenneth L. Clarkson, Wolfgang Mulzer, and C. Seshadhri · 2010
Cited alongside, same era.
Ranking with submodular valuations
Yossi Azar and Iftah Gamzu · 2011
Cited alongside, same era.
A note on the generalized min-sum set cover problem
Martin Skutella and David P. Williamson · 2011
Cited alongside, same era.
A stochastic probing problem with applications
Anupam Gupta and Viswanath Nagarajan · 2013
Cited alongside, same era.
Mechanism design and approximation
Jason D Hartline · 2013
Cited alongside, same era.
Analytical approach to parallel repetition
Irit Dinur and David Steurer · 2014
Cited alongside, same era.
Preemptive and non-preemptive generalized min sum set cover
A PAC approach to application-specific algorithm selection
Rishi Gupta and Tim Roughgarden · 2017
Later among the works it cites.
Efficiency through procrastination: Approximately optimal algorithm configuration with runtime guarantees
Robert Kleinberg, Kevin Leyton-Brown, and Brendan Lucier · 2017
Later among the works it cites.
Learning to branch
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik · 2018
Later among the works it cites.
Dispersion for data-driven algorithm design, online learning, and private optimization
Maria-Florina Balcan, Travis Dick, and Ellen Vitercik · 2018
Later among the works it cites.
Competitive caching with machine learned advice
Thodoris Lykouris and Sergei Vassilvitskii · 2018
Later among the works it cites.
Improving online algorithms via ML predictions
Manish Purohit, Zoya Svitkina, and Ravi Kumar · 2018
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Sungjin Im, Maxim Sviridenko, and Ruben Van Der Zwaan · 2014
Cited alongside, same era.
Sequential information maximization: When is greedy near-optimal?
Yuxin Chen, S. Hamed Hassani, Amin Karbasi, and Andreas Krause · 2015
Cited alongside, same era.
Submodular surrogates for value of information
Yuxin Chen, Shervin Javdani, Amin Karbasi, J. Andrew Bagnell, Siddhartha S. Srinivasa, and Andreas Krause · 2015
Cited alongside, same era.
Submodular stochastic probing on matroids
Marek Adamczyk, Maxim Sviridenko, and Justin Ward · 2016
Cited alongside, same era.
Algorithms and adaptivity gaps for stochastic probing
Anupam Gupta, Viswanath Nagarajan, and Sahil Singla · 2016
Cited alongside, same era.
Learning-theoretic foundations of algorithm configuration for combinatorial partitioning problems
Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White · 2017
Cited alongside, same era.
Later among the works it cites.
The price of information in combinatorial optimization
Sahil Singla · 2018
Later among the works it cites.
Leapsandbounds: A method for approximately optimal algorithm configuration
Gellert Weisz, Andras Gyorgy, and Csaba Szepesvari · 2018
Later among the works it cites.
Learning to prune: Speeding up repeated computations
Daniel Alabi, Adam Tauman Kalai, Katrina Ligett, Cameron Musco, Christos Tzamos, and Ellen Vitercik · 2019
Closest in time.
The markovian price of information
Anupam Gupta, Haotian Jiang, Ziv Scully, and Sahil Singla · 2019
Closest in time.
Online algorithms for rent-or-buy with expert advice
Sreenivas Gollapudi and Debmalya Panigrahi · 2019
Closest in time.
Learning-based frequency estimation algorithms
Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian · 2019
Closest in time.