Image de couverture de livre

ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Rohwedder, Lars
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
par: Eisenbrand, Friedrich, et autres
Publié: (2024)

Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling
par: Rohwedder, Lars, et autres
Publié: (2024)

A k-swap Local Search for Makespan Scheduling
par: Rohwedder, Lars, et autres
Publié: (2024)

An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange
par: Jansen, Bart M. P., et autres
Publié: (2025)

Space-Efficient Algorithm for Integer Programming with Few Constraints
par: Rohwedder, Lars, et autres
Publié: (2024)

Non-Adaptive Evaluation of $k$-of-$n$ Functions: Tight Gap and a Unit-Cost PTAS
par: Nielsen, Mads Anker, et autres
Publié: (2025)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
par: Dai, Han, et autres
Publié: (2025)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
par: Bringmann, Karl, et autres
Publié: (2026)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
par: An, Shinwoo, et autres
Publié: (2024)

Tighter Bounds on Non-clairvoyant Parallel Machine Scheduling with Prediction to Minimize Makespan
par: Chen, Tianqi, et autres
Publié: (2025)

Online Makespan Minimization: Beat LPT by Dynamic Locking
par: Wang, Zhaozi, et autres
Publié: (2023)

FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares
par: Jansen, Klaus, et autres
Publié: (2024)

Minimizing Makespan in Sublinear Time via Weighted Random Sampling
par: Fu, Bin, et autres
Publié: (2026)

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
par: Armbruster, Alexander, et autres
Publié: (2025)

Randomized Rounding over Dynamic Programs
par: Bamas, Etienne, et autres
Publié: (2025)

Cost Preserving Dependent Rounding for Allocation Problems
par: Rohwedder, Lars, et autres
Publié: (2025)

The Submodular Santa Claus Problem
par: Bamas, Etienne, et autres
Publié: (2024)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
par: Mömke, Tobias, et autres
Publié: (2024)

Minimizing the Weighted Makespan with Restarts on a Single Machine
par: Amouzandeh, Aflatoun, et autres
Publié: (2025)

3.415-Approximation for Coflow Scheduling via Iterated Rounding
par: Rohwedder, Lars, et autres
Publié: (2025)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
par: Rohwedder, Lars, et autres
Publié: (2024)

Fast Makespan Minimization via Short ILPs
par: Hermelin, Danny, et autres
Publié: (2026)

An FPT Constant-Factor Approximation Algorithm for Correlation Clustering
par: Zhou, Jianqi, et autres
Publié: (2025)

A Single Exponential-Time FPT Algorithm for Cactus Contraction
par: Krithika, R., et autres
Publié: (2025)

Online Makespan Scheduling under Scenarios
par: Ergen, Ekin
Publié: (2025)

Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
par: Geng, Yutong, et autres
Publié: (2025)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
par: Norose, Ryoma, et autres
Publié: (2024)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
par: Kisfaludi-Bak, Sándor, et autres
Publié: (2020)

FPT Approximations for Connected Maximum Coverage
par: Inamdar, Tanmay, et autres
Publié: (2026)

FPT Approximation for Capacitated Sum of Radii
par: Jaiswal, Ragesh, et autres
Publié: (2024)

Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines
par: Heeger, Klaus, et autres
Publié: (2024)

An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems
par: Murakami, Hitoshi, et autres
Publié: (2024)

FPT Constant Approximation Algorithms for Colorful Sum of Radii
par: Liu, Shuilian, et autres
Publié: (2025)

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
par: Bandyapadhyay, Sayan, et autres
Publié: (2023)

Optimal FPT-Approximability for Modular Linear Equations
par: Dabrowski, Konrad K., et autres
Publié: (2026)

FPT approximations for Capacitated Sum of Radii and Diameters
par: Filtser, Arnold, et autres
Publié: (2024)

An FPT algorithm for Matching Cut and d-cut
par: Aravind, N R, et autres
Publié: (2021)

Improved FPT Approximation for Non-metric TSP
par: Bampis, Evripidis, et autres
Publié: (2024)

Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting
par: Avila, Tatiana Rocha, et autres
Publié: (2026)

Simplified Tight Bounds for Monotone Minimal Perfect Hashing
par: Kosolobov, Dmitry
Publié: (2024)