Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines

DOI10.4230/lipics.isaac.2020.18arXiv2009.11840OpenAlexW3115671652MaRDI QIDQ6065415

Martin Koutecký, Johannes Zink

Publication date: 14 November 2023

Full work available at URL: https://arxiv.org/abs/2009.11840

zbMATH Keywords

schedulinghardnessparameterized complexitycutting stock

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (2)

Fair and efficient allocation with few agent types, few item types, or small value levels ⋮ Block-structured integer programming: can we parameterize without the largest coefficient?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• New algorithms for minimizing the weighted number of tardy jobs on a single machine
• Scheduling and fixed-parameter tractability
• An application of simultaneous diophantine approximation in combinatorial optimization
• On the optimality of exact and approximation algorithms for scheduling problems
• Parameterized complexity of machine scheduling: 15 open problems
• Bin packing with fixed number of bins revisited
• On the parameterized tractability of single machine scheduling with rejection
• Scheduling meets \(n\)-fold integer programming
• Integer Programming
• A Linear Programming Approach to the Cutting-Stock Problem
• About the Structure of the Integer Cone and its Application to Bin Packing
• Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding
• New Algorithmic Results for Bin Packing and Scheduling
• Polynomiality for Bin Packing with a Constant Number of Item Types
• Parameterized Algorithms
• Minimum Makespan Scheduling with Low Rank Processing Times

This page was built for publication: Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines