Cover Image

Cost Preserving Dependent Rounding for Allocation Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Rohwedder, Lars, Rouhani, Arman, Wennmann, Leo
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting
by: Avila, Tatiana Rocha, et al.
Published: (2026)

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

3.415-Approximation for Coflow Scheduling via Iterated Rounding
by: Rohwedder, Lars, et al.
Published: (2025)

ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
by: Rohwedder, Lars
Published: (2025)

The Submodular Santa Claus Problem
by: Bamas, Etienne, et al.
Published: (2024)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
by: Fischer, Nick, et al.
Published: (2024)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
by: Eisenbrand, Friedrich, et al.
Published: (2024)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
by: Rohwedder, Lars, et al.
Published: (2024)

Non-Adaptive Evaluation of $k$-of-$n$ Functions: Tight Gap and a Unit-Cost PTAS
by: Nielsen, Mads Anker, et al.
Published: (2025)

Space-Efficient Algorithm for Integer Programming with Few Constraints
by: Rohwedder, Lars, et al.
Published: (2024)

A Simple Algorithm for Trimmed Multipoint Evaluation
by: Fischer, Nick, et al.
Published: (2025)

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
by: Armbruster, Alexander, et al.
Published: (2025)

Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling
by: Rohwedder, Lars, et al.
Published: (2024)

A k-swap Local Search for Makespan Scheduling
by: Rohwedder, Lars, et al.
Published: (2024)

Fixed Order Scheduling with Deadlines
by: Berger, Andre, et al.
Published: (2024)

Distributed Santa Claus via Global Rounding
by: de Vos, Tijn, et al.
Published: (2026)

Solving Polynomial Equations Over Finite Fields
by: Dell, Holger, et al.
Published: (2024)

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

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

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

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

Accelerated Relax-and-Round for Concave Coverage Problems
by: Fahrbach, Matthew, et al.
Published: (2026)

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

Multiplicative assignment with upgrades
by: Armbruster, Alexander, et al.
Published: (2025)

Variations on the Problem of Identifying Spectrum-Preserving String Sets
by: Chakraborty, Sankardeep, et al.
Published: (2026)

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

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

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

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

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

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

Online Joint Replenishment Problem with Arbitrary Holding and Backlog Costs
by: Azar, Yossi, et al.
Published: (2025)

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

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

Matroid-Based TSP Rounding for Half-Integral Solutions
by: Gupta, Anupam, et al.
Published: (2021)

Log Diameter Rounds MST Verification and Sensitivity in MPC
by: Coy, Sam, et al.
Published: (2024)

An Approximation Algorithm for Monotone Submodular Cost Allocation
by: Mizutani, Ryuhei
Published: (2025)

Round-efficient Fully-scalable MPC algorithms for k-Means
by: Jiang, Shaofeng H. -C., et al.
Published: (2026)

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

On Approximation of Robust Max-Cut and Related Problems using Randomized Rounding Algorithms
by: Shi, Haoyan, et al.
Published: (2024)