Cover Image

Prophet Upper Bounds for Online Matching and Auctions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Soto, José, Verdugo, Victor
Format:	Preprint
Published:	2024
Subjects:	Computer Science and Game Theory Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

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)

Repeated Descent: A Framework for Online Budget-Feasible Auctions
by: Charalampopoulos, Andreas, et al.
Published: (2026)

Private Interdependent Valuations: New Bounds for Single-Item Auctions and Matroids
by: Eden, Alon, et al.
Published: (2024)

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

A Competitive Posted-Price Mechanism for Online Budget-Feasible Auctions
by: Charalampopoulos, Andreas, et al.
Published: (2025)

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

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

Online Proportional Apportionment
by: Cembrano, Javier, et al.
Published: (2025)

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)

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

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

Fairness and Efficiency in Online Class Matching
by: Hajiaghayi, MohammadTaghi, et al.
Published: (2024)

Edge-Weighted Online Bipartite Matching
by: Fahrbach, Matthew, et al.
Published: (2020)

Online Matching Meets Sampling Without Replacement
by: Huang, Zhiyi, et al.
Published: (2024)

Truthful Matching with Online Items and Offline Agents
by: Feldman, Michal, et al.
Published: (2022)

Risk-Sensitive Online Selection with Bounded Adaptivity
by: Nekouyan, Hossein, et al.
Published: (2025)

A Strongly Polynomial Algorithm for Arctic Auctions
by: Garg, Jugal, et al.
Published: (2026)

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

Online Combinatorial Allocations and Auctions with Few Samples
by: Dütting, Paul, et al.
Published: (2024)

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

Beyond the Half-Approximation: Fair and Efficient Online Class Matching
by: Borst, Sander, et al.
Published: (2026)

Edge-weighted Online Stochastic Matching Under Jaillet-Lu LP
by: Yan, Shuyi
Published: (2025)

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

Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms
by: Ezra, Tomer, et al.
Published: (2024)

Edge-weighted Online Stochastic Matching: Beating $1-\frac1e$
by: Yan, Shuyi
Published: (2022)

Online Algorithm for Fractional Matchings with Edge Arrivals in Graphs of Maximum Degree Three
by: Pashkovich, Kanstantsin, et al.
Published: (2026)

Revisiting Ranking for Online Bipartite Matching with Random Arrivals: the Primal-Dual Analysis
by: Peng, Bo, et al.
Published: (2025)

Complexity of Auctions with Interdependence
by: Loiseau, Patrick, et al.
Published: (2026)

Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems
by: Kevi, Eniko, et al.
Published: (2024)

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

Robust Popular Matchings
by: Bullinger, Martin, et al.
Published: (2024)

Stable Matching with Interviews
by: Ashlagi, Itai, et al.
Published: (2025)

Stable Matching with Deviators and Conformists
by: Glitzner, Frederik, et al.
Published: (2026)

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