Copertina

Online Stochastic Matching with Unknown Arrival Order: Beating $0.5$ against the Online Optimum

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Sun, Enze, Tang, Zhihao Gavin, Wang, Yifan
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Combinatorial Philosopher Inequalities
di: Sun, Enze, et al.
Pubblicazione: (2025)

Online Matching: A Brief Survey
di: Huang, Zhiyi, et al.
Pubblicazione: (2024)

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

A Nonparametric Framework for Online Stochastic Matching with Correlated Arrivals
di: Aouad, Ali, et al.
Pubblicazione: (2022)

Online Multi-level Aggregation with Delays and Stochastic Arrivals
di: Mari, Mathieu, et al.
Pubblicazione: (2024)

Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model
di: Burathep, Kunanon, et al.
Pubblicazione: (2025)

Setting Targets is All You Need:Improved Order Competitive Ratio for Online Selection
di: Chen, Liyan, et al.
Pubblicazione: (2024)

Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs
di: Jiang, Tianle, et al.
Pubblicazione: (2024)

Stochastic Online Correlated Selection
di: Chen, Ziyun, et al.
Pubblicazione: (2024)

Approximating Optimum Online for Capacitated Resource Allocation
di: Braun, Alexander, et al.
Pubblicazione: (2024)

Online Makespan Minimization: Beat LPT by Dynamic Locking
di: Wang, Zhaozi, et al.
Pubblicazione: (2023)

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

Online Rounding for Set Cover under Subset Arrivals
di: Byrka, Jarosław, et al.
Pubblicazione: (2025)

Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
di: Geng, Yutong, et al.
Pubblicazione: (2025)

When Stochastic Rewards Reduce to Deterministic Rewards in Online Bipartite Matching
di: Udwani, Rajan
Pubblicazione: (2023)

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

Edge-weighted Matching in the Dark
di: Huang, Zhiyi, et al.
Pubblicazione: (2025)

Online $b$-Matching with Stochastic Rewards
di: Albers, Susanne, et al.
Pubblicazione: (2024)

Dynamic Batching of Online Arrivals to Leverage Economies of Scale
di: Bhimaraju, Akhil, et al.
Pubblicazione: (2023)

On the Advice Complexity of Online Matching on the Line
di: Csaba, Béla, et al.
Pubblicazione: (2024)

Online Matching in Geometric Random Graphs
di: Sentenac, Flore, et al.
Pubblicazione: (2023)

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

Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization
di: Nikolov, Aleksandar, et al.
Pubblicazione: (2026)

Almost Tight Bounds for Online Hypergraph Matching
di: Tröbst, Thorben, et al.
Pubblicazione: (2024)

Online Metric Matching: Beyond the Worst Case
di: Yang, Mingwei, et al.
Pubblicazione: (2024)

Online Matching with Delays and Size-based Costs
di: Kawase, Yasushi, et al.
Pubblicazione: (2024)

Online Weighted Paging with Unknown Weights
di: Levy, Orin, et al.
Pubblicazione: (2024)

Online Allocation with Unknown Shared Supply
di: Neoh, Tzeh Yuan, et al.
Pubblicazione: (2026)

Nearly Optimal Bounds for Stochastic Online Sorting
di: Hu, Yang
Pubblicazione: (2025)

Randomized Rounding Approaches to Online Allocation, Sequencing, and Matching
di: Ma, Will
Pubblicazione: (2024)

The Power of Greedy for Online Minimum Cost Matching on the Line
di: Balkanski, Eric, et al.
Pubblicazione: (2022)

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
di: Joseph, et al.
Pubblicazione: (2023)

Near-optimal Algorithms for Stochastic Online Bin Packing
di: Ayyadevara, Nikhil, et al.
Pubblicazione: (2022)

Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
di: Buchbinder, Niv, et al.
Pubblicazione: (2026)

Degree-bounded Online Bipartite Matching: OCS vs. Ranking
di: Feng, Yilong, et al.
Pubblicazione: (2025)

A New Impossibility Result for Online Bipartite Matching Problems
di: Chierichetti, Flavio, et al.
Pubblicazione: (2025)

On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
di: Liu, Yang P.
Pubblicazione: (2024)

Optimizing Inventory Placement for a Downstream Online Matching Problem
di: Epstein, Boris, et al.
Pubblicazione: (2024)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
di: Kalavas, Andreas, et al.
Pubblicazione: (2025)