Archit Bubna

dblp:332/6207 · DBLP profile ↗
← Back
1ranked-venue papers
1as first author
1since 2021 · last 2023
0009-0008-6179-6651ORCID · reported

Domains — the database's venue-derived domains; a paper can count in several

Artificial intelligence and machine learning · 1 · 1 first-author · 1 since 2021Theory of computation · 1 · 1 first-author · 1 since 2021

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Approximation and online algorithms · 75% Information theory · 25%

Topics — the 4 heaviest of 4, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Approximation and online algorithms › online algorithms
competitive analysis
0.712023
Prophet Inequality: Order selection beats random order · EC 2023
Information theory › statistical inference › model selection
model order selection
0.712023
Prophet Inequality: Order selection beats random order · EC 2023
Approximation and online algorithms
online selection
0.712023
Prophet Inequality: Order selection beats random order · EC 2023
Approximation and online algorithms › online algorithms
prophet inequality
0.712023
Prophet Inequality: Order selection beats random order · EC 2023

Methods — techniques the papers use, named apart from their topics

stochastic optimization · 0.7
YearPublicationVenuePosition
2023 Prophet Inequality: Order selection beats random order
abstract
In the prophet inequality problem, a gambler faces a sequence of items arriving online with values drawn independently from known distributions. On seeing an item, the gambler must choose whether to accept its value as her reward and quit the game, or reject it and continue. The gambler's aim is to maximize her expected reward relative to the expected maximum of the values of all items. Since the seventies, a tight bound of 1/2 has been known for this competitive ratio in the setting where the items arrive in an adversarial order [Krengel and Sucheston, 1977, 1978]. However, the optimum ratio still remains unknown in the order selection setting, where the gambler selects the arrival order, as well as in prophet secretary, where the items arrive in a random order. Moreover, it is not even known whether a separation exists between the two settings.
Archit Bubna, Ashish Chiplunkar
EC1