Kristen Kessel

dblp:298/1372 · DBLP profile ↗
← Back
1ranked-venue papers
1as first author
1since 2021 · last 2022
—ORCID · none

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 · 50% Algorithmic game theory and mechanism design · 50%

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

TopicWeightPapersLastEvidence papers
Algorithmic game theory and mechanism design
dynamic pricing
0.612022
The Stationary Prophet Inequality Problem · EC 2022
Approximation and online algorithms
online algorithms
0.612022
The Stationary Prophet Inequality Problem · EC 2022
Algorithmic game theory and mechanism design
pricing
0.612022
The Stationary Prophet Inequality Problem · EC 2022
Approximation and online algorithms › online algorithms
prophet inequality
0.612022
The Stationary Prophet Inequality Problem · EC 2022

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

prophet inequality · 0.6approximation algorithm · 0.6
YearPublicationVenuePosition
2022 The Stationary Prophet Inequality Problem
abstract
We study a continuous and infinite time horizon counterpart to the classic prophet inequality, which we term the stationary prophet inequality problem. Here, copies of a good arrive and perish according to Poisson point processes. Buyers arrive similarly and make take-it-or-leave-it offers for unsold items. The objective is to maximize the (infinite) time average revenue of the seller. Our main results are pricing-based policies which (i) achieve a 1/2-approximation of the optimal offline policy, which is best possible, and (ii) achieve a better than (1-1/e)-approximation of the optimal online policy. Result (i) improves upon bounds implied by recent work of Collina et al. (WINE'20), and is the first optimal prophet inequality for a stationary problem. Result (ii) improves upon a 1-1/e bound implied by recent work of Aouad and Sarita (EC'20), and shows that this prevalent bound in online algorithms is not optimal for this problem.
Kristen Kessel, Ali Shameli, Amin Saberi, David Wajc
EC1