Buchumschlag

A Bicriterion Concentration Inequality and Prophet Inequalities for $k$-Fold Matroid Unions

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Alon, Noga, Gravin, Nick, Pollner, Tristan, Rubinstein, Aviad, Wang, Hongao, Weinberg, S. Matthew, Zhang, Qianfan
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms Probability
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Optimal Single-Choice Prophet Inequalities from Samples
von: Rubinstein, Aviad, et al.
Veröffentlicht: (2019)

Sample-Based Matroid Prophet Inequalities
von: Fu, Hu, et al.
Veröffentlicht: (2024)

Beyond matroids: Secretary Problem and Prophet Inequality with general constraints
von: Rubinstein, Aviad
Veröffentlicht: (2016)

Threshold Rules for the Classical Prophet Inequality
von: Zhang, Jiechen
Veröffentlicht: (2026)

Lookback Prophet Inequalities
von: Benomar, Ziyad, et al.
Veröffentlicht: (2024)

New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling
von: Braverman, Mark, et al.
Veröffentlicht: (2024)

Prophet Inequalities over Time
von: Abels, Andreas, et al.
Veröffentlicht: (2022)

Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
von: Rubinstein, Aviad, et al.
Veröffentlicht: (2026)

Parallel Sampling via Counting
von: Anari, Nima, et al.
Veröffentlicht: (2024)

The $k$-Fold Matroid Secretary Problem
von: Gujjar, Rishi, et al.
Veröffentlicht: (2025)

New Prophet Inequalities via Poissonization and Sharding
von: Harb, Elfarouk
Veröffentlicht: (2023)

The Localization Method for High-Dimensional Inequalities
von: Kook, Yunbum, et al.
Veröffentlicht: (2025)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
von: Mao, Xiao, et al.
Veröffentlicht: (2026)

Prophet Inequalities: Separating Random Order from Order Selection
von: Giambartolomei, Giordano, et al.
Veröffentlicht: (2023)

Random Matrices, Intrinsic Freeness, and Sharp Non-Asymptotic Inequalities
von: Bandeira, Afonso S.
Veröffentlicht: (2025)

Combinatorial Stationary Prophet Inequalities
von: Patel, Neel, et al.
Veröffentlicht: (2023)

Prophet Inequalities with Cancellation Costs
von: Ekbatani, Farbod, et al.
Veröffentlicht: (2024)

Optimal Rounding for Two-Stage Bipartite Matching
von: Pollner, Tristan, et al.
Veröffentlicht: (2025)

Residual Prophet Inequalities
von: Correa, Jose, et al.
Veröffentlicht: (2025)

IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates
von: Giambartolomei, Giordano, et al.
Veröffentlicht: (2024)

Multi-Unit Combinatorial Prophet Inequalities
von: Chawla, Shuchi, et al.
Veröffentlicht: (2025)

New Approximation Guarantees for The Inventory Staggering Problem
von: Alon, Noga, et al.
Veröffentlicht: (2025)

Truthful, Credible, and Optimal Auctions for Matroids via Blockchains and Commitments
von: Ganesh, Aadityan, et al.
Veröffentlicht: (2025)

Approximating Maximum Matching Requires Almost Quadratic Time
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Threshold Testing and Semi-Online Prophet Inequalities
von: Hoefer, Martin, et al.
Veröffentlicht: (2023)

Single-Sample Prophet Inequalities via Greedy-Ordered Selection
von: Caramanis, Constantine, et al.
Veröffentlicht: (2021)

Approximating Optimum Online for Capacitated Resource Allocation
von: Braun, Alexander, et al.
Veröffentlicht: (2024)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Sublinear Algorithms for TSP via Path Covers
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2023)

Static Pricing for Single Sample Multi-unit Prophet Inequalities
von: Nuti, Pranav, et al.
Veröffentlicht: (2024)

On Extended Concentration Inequalities for Fast JL Embeddings of Infinite Sets
von: Boahen, Edem, et al.
Veröffentlicht: (2025)

Sampling Proper Colorings on Line Graphs Using $(1+o(1))Δ$ Colors
von: Wang, Yulin, et al.
Veröffentlicht: (2023)

New Bounds for Circular Trace Reconstruction
von: Burudgunte, Arnav, et al.
Veröffentlicht: (2025)

Prophet Inequalities: Competing with the Top $\ell$ Items is Easy
von: Molina, Mathieu, et al.
Veröffentlicht: (2024)

Decay of correlation for edge colorings when $q>3Δ$
von: Chen, Zejia, et al.
Veröffentlicht: (2025)

Improved Mechanisms and Prophet Inequalities for Graphical Dependencies
von: Livanos, Vasilis, et al.
Veröffentlicht: (2024)

Combinatorial Philosopher Inequalities
von: Sun, Enze, et al.
Veröffentlicht: (2025)

Mean-field Potts and random-cluster dynamics from high-entropy initializations
von: Blanca, Antonio, et al.
Veröffentlicht: (2024)

Sampling Sphere Packings with Continuum Glauber Dynamics
von: Kuchukova, Aiya, et al.
Veröffentlicht: (2026)

Discrete Optimal Transport: Rapid Convergence of Simulated Annealing Algorithms
von: He, Yuchen, et al.
Veröffentlicht: (2026)