Copertina

Randomized Rounding over Dynamic Programs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bamas, Etienne, Li, Shi, Rohwedder, Lars
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

The Submodular Santa Claus Problem
di: Bamas, Etienne, et al.
Pubblicazione: (2024)

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

Lift-and-Project Integrality Gaps for Santa Claus
di: Bamas, Etienne
Pubblicazione: (2024)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs
di: Li, Shi
Pubblicazione: (2024)

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

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

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

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

Multiplicative assignment with upgrades
di: Armbruster, Alexander, et al.
Pubblicazione: (2025)

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

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

Sorting and Selection in Rounds with Adversarial Comparisons
di: Trevisan, Chris
Pubblicazione: (2023)

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

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

A Note on Rounding Matchings in General Graphs
di: Dudeja, Aditi
Pubblicazione: (2024)

Differentiable Extensions with Rounding Guarantees for Combinatorial Optimization over Permutations
di: Nerem, Robert R., et al.
Pubblicazione: (2024)

Adaptive Sparsification for Linear Programming
di: Objois, Étienne, et al.
Pubblicazione: (2025)

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

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

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

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

New Convex Programming Technique for Nash Social Welfare and Scheduling
di: Feng, Yuda, et al.
Pubblicazione: (2026)

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

From Dynamic Programs to Greedy Algorithms
di: van Melkebeek, Dieter
Pubblicazione: (2025)

Maintaining Random Assignments under Adversarial Dynamics
di: Haeupler, Bernhard, et al.
Pubblicazione: (2026)

Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
di: Brakensiek, Joshua, et al.
Pubblicazione: (2026)