Imagen de Portada

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Joseph, Naor, Srinivasan, Aravind, Wajc, David
Formato:	Preprint
Publicado:	2023
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
por: Bhattacharya, Sayan, et al.
Publicado: (2023)

Dimension-Free Correlated Sampling for the Hypersimplex
por: Joseph, et al.
Publicado: (2025)

Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
por: Buchbinder, Niv, et al.
Publicado: (2025)

Deterministic Online Bipartite Edge Coloring
por: Blikstad, Joakim, et al.
Publicado: (2024)

Online Matching: A Brief Survey
por: Huang, Zhiyi, et al.
Publicado: (2024)

Proportionally Fair Matching via Randomized Rounding
por: Duppala, Sharmila, et al.
Publicado: (2024)

Optimal Rounding for Two-Stage Bipartite Matching
por: Pollner, Tristan, et al.
Publicado: (2025)

New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling
por: Braverman, Mark, et al.
Publicado: (2024)

Online Edge Coloring: Sharp Thresholds
por: Blikstad, Joakim, et al.
Publicado: (2025)

Online Rounding Schemes for $ k $-Rental Problems
por: Nekouyan, Hossein, et al.
Publicado: (2025)

Online Edge Coloring is (Nearly) as Easy as Offline
por: Blikstad, Joakim, et al.
Publicado: (2024)

Dependent randomized rounding for clustering and partition systems with knapsack constraints
por: Harris, David G., et al.
Publicado: (2017)

Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes
por: Brubach, Brian, et al.
Publicado: (2021)

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

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

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

Non-Linear Paging
por: Doron-Arad, Ilan, et al.
Publicado: (2024)

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

Online Deterministic Minimum Cost Bipartite Matching with Delays on a Line
por: Kuo, Tung-Wei
Publicado: (2024)

Concentration of Submodular Functions and Read-k Families Under Negative Dependence
por: Duppala, Sharmila, et al.
Publicado: (2023)

Sublinear Time Algorithm for Online Weighted Bipartite Matching
por: Hu, Hang, et al.
Publicado: (2022)

Interval-Constrained Bipartite Matching over Time
por: Abels, Andreas, et al.
Publicado: (2024)

Efficient Kernelization Algorithm for Bipartite Graph Matching
por: Wu, Guang, et al.
Publicado: (2024)

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

On the Complexity of the Odd-Red Bipartite Perfect Matching Polytope
por: Nägele, Martin, et al.
Publicado: (2026)

Approximate Bipartite $b$-Matching using Multiplicative Auction
por: Samineni, Bhargav, et al.
Publicado: (2024)

A Note on Rounding Matchings in General Graphs
por: Dudeja, Aditi
Publicado: (2024)

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

An FPT algorithm for Matching Cut and d-cut
por: Aravind, N R, et al.
Publicado: (2021)

Cost Preserving Dependent Rounding for Allocation Problems
por: Rohwedder, Lars, et al.
Publicado: (2025)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
por: Zheng, Da Wei, et al.
Publicado: (2023)

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
por: Azarmehr, Amir, et al.
Publicado: (2024)

Learning-Augmented Online Bipartite Fractional Matching
por: Choo, Davin, et al.
Publicado: (2025)

A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs
por: Kwok, Shawxing
Publicado: (2025)

Bipartite Matching is in Catalytic Logspace
por: Agarwala, Aryan, et al.
Publicado: (2025)

Combinatorial Stationary Prophet Inequalities
por: Patel, Neel, et al.
Publicado: (2023)

Differentially private graph coloring
por: Xie, Michael, et al.
Publicado: (2026)

Barter Exchange with Shared Item Valuations
por: Luque, Juan, et al.
Publicado: (2024)

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

Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model
por: Jin, Billy, et al.
Publicado: (2022)