Empowering the configuration-IP: new PTAS results for scheduling with setup times

DOI10.1007/s10107-021-01694-3OpenAlexW2964184266MaRDI QIDQ2089776

Kim-Manuel Klein, Malin Rau, Klaus Jansen, Marten Maack

Publication date: 24 October 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-021-01694-3

zbMATH Keywords

parallel machinessetup timeEPTAS\(n\)-fold integer programming

Mathematics Subject Classification ID

Integer programming (90C10) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The third comprehensive survey on scheduling problems with setup times/costs
• Lot-sizing scheduling with batch setup times
• Strong LP formulations for scheduling splittable jobs on unrelated machines
• Nonlinear discrete optimization. An algorithmic theory
• Approximation schemes for scheduling on parallel machines
• Non-preemptive scheduling with setup times: a PTAS
• Splitting versus setup trade-offs for scheduling to minimize weighted completion time
• \(n\)-fold integer programming in cubic time
• Combinatorial \(n\)-fold integer programming and applications
• Scheduling meets \(n\)-fold integer programming
• Split scheduling with uniform setup times
• A survey of scheduling problems with setup times or costs
• Integer Programming with a Fixed Number of Variables
• A Linear Programming Approach to the Cutting-Stock Problem
• Closing the Gap for Makespan Scheduling via Sparsification Techniques
• Non-preemptive Scheduling on Machines with Setup Times
• Minkowski's Convex Body Theorem and Integer Programming
• A Better Heuristic for Preemptive Parallel Machine Scheduling with Batch Setup Times
• Analysis of Heuristics for Preemptive Parallel Machine Scheduling with Batch Setup Times
• Faster Algorithms for Integer Programs with Block Structure
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• Polynomiality for Bin Packing with a Constant Number of Item Types
• Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding

This page was built for publication: Empowering the configuration-IP: new PTAS results for scheduling with setup times