ETH-tight FPT algorithm for makespan minimization on uniform machines

DOI10.4230/LIPICS.ICALP.2025.126MaRDI QIDQ7397583zbMATH OpenFDO

Authors Lars Rohwedder

Publication date 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.126

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A colorful Steinitz lemma with application to block-structured integer programs
• An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables
• Closing the gap for makespan scheduling via sparsification techniques
• Combinatorial \(n\)-fold integer programming and applications
• Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
• Faster algorithms for bounded knapsack and bounded subset sum via fine-grained proximity results
• Fine-grained equivalence for problems related to integer linear programming
• scientific article; zbMATH DE number 3708084 (Why is no real title available?)
• scientific article; zbMATH DE number 7788439 (Why is no real title available?)
• Knapsack and subset sum with small items
• On Integer Programming, Discrepancy, and Convolution
• On the optimality of approximation schemes for the classical scheduling problem
• Polynomiality for Bin Packing with a Constant Number of Item Types
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Scheduling and fixed-parameter tractability
• Scheduling meets n-fold integer programming

This page was built for publication: ETH-tight FPT algorithm for makespan minimization on uniform machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7397583)