Cover Image

Approximating Optimum Online for Capacitated Resource Allocation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Braun, Alexander, Kesselheim, Thomas, Pollner, Tristan, Saberi, Amin
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

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

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

Improved Approximations for Stationary Bipartite Matching: Beyond Probabilistic Independence
by: AmaniHamedani, Alireza, et al.
Published: (2024)

Near-Optimal Bayesian Online Assortment of Reusable Resources
by: Feng, Yiding, et al.
Published: (2025)

Supermodular Approximation of Norms and Applications
by: Kesselheim, Thomas, et al.
Published: (2024)

MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation
by: Hayderi, Alexandre, et al.
Published: (2024)

Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives
by: Kesselheim, Thomas, et al.
Published: (2025)

FPT Approximation for Capacitated Sum of Radii
by: Jaiswal, Ragesh, et al.
Published: (2024)

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

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

A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
by: Kang, Suho, 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)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

Improved Approximations for the Unsplittable Capacitated Vehicle Routing Problem
by: Zhao, Jingyang, et al.
Published: (2026)

Multidepot Capacitated Vehicle Routing with Improved Approximation Guarantees
by: Zhao, Jingyang, et al.
Published: (2023)

Enhanced Approximation Algorithms for the Capacitated Location Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

Robustness of Online Inventory Balancing to Inventory Shocks
by: Feng, Yiding, et al.
Published: (2025)

Sublinear Algorithms for TSP via Path Covers
by: Behnezhad, Soheil, et al.
Published: (2023)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
by: Das, Rathish, et al.
Published: (2025)

Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities
by: Lokshtanov, Daniel, et al.
Published: (2024)

Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
by: Zhao, Jingyang, et al.
Published: (2022)

Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding
by: Friggstad, Zachary, et al.
Published: (2025)

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

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

Online Resource Allocation with Cancellations
by: Ekbatani, Farbod, et al.
Published: (2022)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
by: Łącki, Jakub, et al.
Published: (2025)

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

Prophet and Secretary at the Same Time
by: Kehne, Gregory, et al.
Published: (2025)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
by: Gadekar, Ameet, et al.
Published: (2025)

An Efficient Algorithm for Minimizing Ordered Norms in Fractional Load Balancing
by: Blankenburg, Daniel, et al.
Published: (2025)

A Ranking Framework for Network Resource Allocation and Scheduling via Hypergraphs
by: Singh, Rajpreet, et al.
Published: (2025)

Flow-weighted Layered Metric Euclidean Capacitated Steiner Tree Problem
by: Bläsius, Thomas, et al.
Published: (2025)

Efficient Resource Allocation under Adversary Attacks: A Decomposition-Based Approach
by: Davoodi, Mansoor, et al.
Published: (2025)

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
by: Bandyapadhyay, Sayan, et al.
Published: (2023)

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

Bounds on Longest Simple Cycles in Weighted Directed Graphs via Optimum Cycle Means
by: Dasdan, Ali
Published: (2025)

FPT approximations for Capacitated Sum of Radii and Diameters
by: Filtser, Arnold, et al.
Published: (2024)

Competitive Capacitated Online Recoloring
by: Rajaraman, Rajmohan, et al.
Published: (2024)

A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem
by: Xie, Ningyi, et al.
Published: (2023)

Capacitated Partition Vertex Cover and Partition Edge Cover
by: Dabas, Rajni, et al.
Published: (2025)