Cover Image

Randomized Rounding Approaches to Online Allocation, Sequencing, and Matching

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Ma, Will
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

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

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

A Randomized Rounding Approach for DAG Edge Deletion
by: Kalantarzadeh, Sina, et al.
Published: (2025)

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

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

A Note on Rounding Matchings in General Graphs
by: Dudeja, Aditi
Published: (2024)

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

Randomized Rounding over Dynamic Programs
by: Bamas, Etienne, et al.
Published: (2025)

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

$k$-Clustering via Iterative Randomized Rounding
by: Byrka, Jarosław, et al.
Published: (2026)

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

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

A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
by: Kang, Suho, et al.
Published: (2025)

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

Constant-Stretch Rounding on the Hypersimplex
by: Anari, Nima, et al.
Published: (2026)

Adaptive Multi-Round Allocation with Stochastic Arrivals
by: Pan, Yuqi, et al.
Published: (2026)

An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
by: Doron-Arad, Ilan, et al.
Published: (2023)

Course Allocation with Credits via Stable Matching
by: Rodríguez, José, et al.
Published: (2025)

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

Online Allocation with Concave, Diminishing-Returns Objectives
by: Patton, Kalen
Published: (2025)

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

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

Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources
by: Goyal, Vineet, et al.
Published: (2020)

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

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

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

Online Algorithms with Randomly Infused Advice
by: Emek, Yuval, et al.
Published: (2023)

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

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

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

Sorting and Selection in Rounds with Adversarial Comparisons
by: Trevisan, Chris
Published: (2023)

Cut-Query Algorithms with Few Rounds
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

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

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

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

Online Disjoint Set Covers: Randomization is not Necessary
by: Bienkowski, Marcin, et al.
Published: (2024)

Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations
by: Hathcock, Daniel, et al.
Published: (2025)

Weighted Matching in the Random-Order Streaming and Robust Communication Models
by: Hashemi, Diba, et al.
Published: (2024)

A Unified Framework for Analysis of Randomized Greedy Matching Algorithms
by: Derakhshan, Mahsa, et al.
Published: (2026)

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