Cover Image

New Prophet Inequalities via Poissonization and Sharding

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Harb, Elfarouk
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems
by: Harb, Elfarouk, et al.
Published: (2025)

Lookback Prophet Inequalities
by: Benomar, Ziyad, et al.
Published: (2024)

Shortest Path Separators in Unit Disk Graphs
by: Harb, Elfarouk, et al.
Published: (2024)

Prophet Inequalities over Time
by: Abels, Andreas, et al.
Published: (2022)

Sample-Based Matroid Prophet Inequalities
by: Fu, Hu, et al.
Published: (2024)

Threshold Rules for the Classical Prophet Inequality
by: Zhang, Jiechen
Published: (2026)

A Bicriterion Concentration Inequality and Prophet Inequalities for $k$-Fold Matroid Unions
by: Alon, Noga, et al.
Published: (2024)

Combinatorial Stationary Prophet Inequalities
by: Patel, Neel, et al.
Published: (2023)

Prophet Inequalities with Cancellation Costs
by: Ekbatani, Farbod, et al.
Published: (2024)

Multi-Unit Combinatorial Prophet Inequalities
by: Chawla, Shuchi, et al.
Published: (2025)

Single-Sample Prophet Inequalities via Greedy-Ordered Selection
by: Caramanis, Constantine, et al.
Published: (2021)

Residual Prophet Inequalities
by: Correa, Jose, et al.
Published: (2025)

Threshold Testing and Semi-Online Prophet Inequalities
by: Hoefer, Martin, et al.
Published: (2023)

Optimal Single-Choice Prophet Inequalities from Samples
by: Rubinstein, Aviad, et al.
Published: (2019)

Beyond matroids: Secretary Problem and Prophet Inequality with general constraints
by: Rubinstein, Aviad
Published: (2016)

Static Pricing for Single Sample Multi-unit Prophet Inequalities
by: Nuti, Pranav, et al.
Published: (2024)

New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling
by: Braverman, Mark, et al.
Published: (2024)

ε-Cost Sharding: Scaling Hypergraph-Based Static Functions and Filters to Trillions of Keys
by: Vigna, Sebastiano
Published: (2025)

Minimization I.I.D. Prophet Inequality via Extreme Value Theory: A Unified Approach
by: Livanos, Vasilis, et al.
Published: (2024)

Prophet Inequalities: Competing with the Top $\ell$ Items is Easy
by: Molina, Mathieu, et al.
Published: (2024)

Improved Mechanisms and Prophet Inequalities for Graphical Dependencies
by: Livanos, Vasilis, et al.
Published: (2024)

Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality
by: Liu, Junyan, et al.
Published: (2025)

Combinatorial Philosopher Inequalities
by: Sun, Enze, et al.
Published: (2025)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
by: Jin, Ce, et al.
Published: (2024)

A Poisson Process for Submodular Maximization
by: Rozenman, Amit Ganz, et al.
Published: (2026)

Prophet and Secretary at the Same Time
by: Kehne, Gregory, et al.
Published: (2025)

Trading Prophets with Initial Capital
by: Azar, Yossi, et al.
Published: (2025)

Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
by: Rubinstein, Aviad, et al.
Published: (2026)

The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis
by: Kuszmaul, William, et al.
Published: (2021)

Prophet Secretary and Matching: the Significance of the Largest Item
by: Chen, Ziyun, et al.
Published: (2024)

Prophet Upper Bounds for Online Matching and Auctions
by: Soto, José, et al.
Published: (2024)

Trading Prophets: How to Trade Multiple Stocks Optimally
by: Rajput, Surbhi, et al.
Published: (2025)

New Diameter Approximations via Distance Oracle Techniques
by: Kirkpatrick, Yael, et al.
Published: (2026)

Prophet Inequalities: Separating Random Order from Order Selection
by: Giambartolomei, Giordano, et al.
Published: (2023)

Eigenpath traversal by Poisson-distributed phase randomisation
by: Cunningham, Joseph, et al.
Published: (2024)

New results for the detection of bicliques
by: Manoussakis, George
Published: (2024)

New weighted additive spanners
by: La, An, et al.
Published: (2024)

New Greedy Spanners and Applications
by: Popova, Elizaveta, et al.
Published: (2026)

Data subsampling for Poisson regression with pth-root-link
by: Lie, Han Cheng, et al.
Published: (2024)

New approximate distance oracles and their applications
by: Kadria, Avi, et al.
Published: (2025)