Buchumschlag

New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Braverman, Mark, Derakhshan, Mahsa, Pollner, Tristan, Saberi, Amin, Wajc, David
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

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

A Unified Framework for Analysis of Randomized Greedy Matching Algorithms
von: Derakhshan, Mahsa, et al.
Veröffentlicht: (2026)

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
von: Joseph, et al.
Veröffentlicht: (2023)

Online Matching: A Brief Survey
von: Huang, Zhiyi, et al.
Veröffentlicht: (2024)

Improved Approximations for Stationary Bipartite Matching: Beyond Probabilistic Independence
von: AmaniHamedani, Alireza, et al.
Veröffentlicht: (2024)

Near-Optimal Bayesian Online Assortment of Reusable Resources
von: Feng, Yiding, et al.
Veröffentlicht: (2025)

MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation
von: Hayderi, Alexandre, et al.
Veröffentlicht: (2024)

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

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

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Deterministic Online Bipartite Edge Coloring
von: Blikstad, Joakim, et al.
Veröffentlicht: (2024)

Online Edge Coloring: Sharp Thresholds
von: Blikstad, Joakim, et al.
Veröffentlicht: (2025)

Online Edge Coloring is (Nearly) as Easy as Offline
von: Blikstad, Joakim, et al.
Veröffentlicht: (2024)

Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
von: Buchbinder, Niv, et al.
Veröffentlicht: (2025)

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

A Simple Analysis of Ranking in General Graphs
von: Derakhshan, Mahsa, et al.
Veröffentlicht: (2025)

Improved Approximation for Ranking on General Graphs
von: Derakhshan, Mahsa, et al.
Veröffentlicht: (2025)

Dimension-Free Correlated Sampling for the Hypersimplex
von: Joseph, et al.
Veröffentlicht: (2025)

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

Tight Analyses of Ordered and Unordered Linear Probing
von: Braverman, Mark, et al.
Veröffentlicht: (2025)

Approximation Algorithms for Action-Reward Query-Commit Matching
von: Derakhshan, Mahsa, et al.
Veröffentlicht: (2026)

Robustness of Online Inventory Balancing to Inventory Shocks
von: Feng, Yiding, et al.
Veröffentlicht: (2025)

Stable Matching with Interviews
von: Ashlagi, Itai, et al.
Veröffentlicht: (2025)

Linear Programming Based Near-Optimal Pricing for Laminar Bayesian Online Selection
von: Anari, Nima, et al.
Veröffentlicht: (2018)

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

A New Impossibility Result for Online Bipartite Matching Problems
von: Chierichetti, Flavio, et al.
Veröffentlicht: (2025)

Pivot based correlation clustering in the presence of good clusters
von: Lolck, David Rasmussen, et al.
Veröffentlicht: (2026)

Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion
von: Li, Yingxi, et al.
Veröffentlicht: (2025)

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

Correlation Clustering Beyond the Pivot Algorithm
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Online Learning with Limited Information in the Sliding Window Model
von: Braverman, Vladimir, et al.
Veröffentlicht: (2026)

On the Advice Complexity of Online Matching on the Line
von: Csaba, Béla, et al.
Veröffentlicht: (2024)

Online Matching in Geometric Random Graphs
von: Sentenac, Flore, et al.
Veröffentlicht: (2023)

A New Information Complexity Measure for Multi-pass Streaming with Applications
von: Braverman, Mark, et al.
Veröffentlicht: (2024)

Optimality of Frequency Moment Estimation
von: Braverman, Mark, et al.
Veröffentlicht: (2024)

Almost Tight Bounds for Online Hypergraph Matching
von: Tröbst, Thorben, et al.
Veröffentlicht: (2024)

Online Metric Matching: Beyond the Worst Case
von: Yang, Mingwei, et al.
Veröffentlicht: (2024)

Online Matching with Delays and Size-based Costs
von: Kawase, Yasushi, et al.
Veröffentlicht: (2024)

Course Allocation with Credits via Stable Matching
von: Rodríguez, José, et al.
Veröffentlicht: (2025)