Cover Image

Sample-Based Matroid Prophet Inequalities

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fu, Hu, Lu, Pinyan, Tang, Zhihao Gavin, Wu, Hongxun, Wu, Jinzhao, Zhang, Qianfan
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

Truthful, Credible, and Optimal Auctions for Matroids via Blockchains and Commitments
by: Ganesh, Aadityan, et al.
Published: (2025)

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

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

New Prophet Inequalities via Poissonization and Sharding
by: Harb, Elfarouk
Published: (2023)

A Faster Algorithm for Pigeonhole Equal Sums
by: Jin, Ce, et al.
Published: (2024)

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

Optimal quantile estimation: beyond the comparison model
by: Gupta, Meghal, et al.
Published: (2024)

Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds
by: Huang, Lingxiao, et al.
Published: (2023)

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

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

Online Matching: A Brief Survey
by: Huang, Zhiyi, et al.
Published: (2024)

Online Stochastic Matching with Unknown Arrival Order: Beating $0.5$ against the Online Optimum
by: Sun, Enze, et al.
Published: (2025)

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

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

Dynamic Matroids: Base Packing and Covering
by: de Vos, Tijn, et al.
Published: (2025)

Local Search for Clustering in Almost-linear Time
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

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

Efficiently Coloring the Intersection of a General Matroid and Partition Matroids
by: Arndt, Stephen, et al.
Published: (2025)

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

Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation
by: Hellerstein, Lisa, et al.
Published: (2026)

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

The Cost of Parallelizing Boosting
by: Lyu, Xin, et al.
Published: (2024)

Matroid-Based TSP Rounding for Half-Integral Solutions
by: Gupta, Anupam, et al.
Published: (2021)

Optimal Competitive Ratio of Two-sided Online Bipartite Matching
by: Tang, Zhihao Gavin
Published: (2026)

Multiagent Matroid Upgrading: Greedy is Fair and Efficient
by: Ma, Qingwen, et al.
Published: (2026)

Matroid Secretary via Labeling Schemes
by: Bérczi, Kristóf, et al.
Published: (2024)

The $k$-Fold Matroid Secretary Problem
by: Gujjar, Rishi, et al.
Published: (2025)

Faster Approximate Linear Matroid Intersection
by: Terao, Tatsuya
Published: (2026)

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

Fault-Tolerant Matroid Bases
by: Bentert, Matthias, et al.
Published: (2025)

On the Parallel Complexity of Finding a Matroid Basis
by: Khanna, Sanjeev, et al.
Published: (2025)

Improved Algorithms for Fair Matroid Submodular Maximization
by: Mahabadi, Sepideh, et al.
Published: (2026)

A Weighted-to-Unweighted Reduction for Matroid Intersection
by: Dudeja, Aditi, et al.
Published: (2026)

Stochastic Minimum Spanning Trees with a Single Sample
by: Hoeksma, Ruben, et al.
Published: (2024)

Subquadratic Submodular Maximization with a General Matroid Constraint
by: Kobayashi, Yusuke, et al.
Published: (2024)

Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
by: Inamdar, Tanmay, et al.
Published: (2024)