scientific article; zbMATH DE number 7559087

DOI10.4230/LIPIcs.ITCS.2019.44MaRDI QIDQ5090421

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

Publication date: 18 July 2022

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (14)

About the Complexity of Two-Stage Stochastic IPs ⋮ Tightness of sensitivity and proximity bounds for integer linear programs ⋮ Approximation schemes for the generalized extensible bin packing problem ⋮ A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ High-multiplicity \(N\)-fold IP via configuration LP ⋮ EPTAS for parallel identical machine scheduling with time restrictions ⋮ Block-structured integer programming: can we parameterize without the largest coefficient? ⋮ Unnamed Item ⋮ Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding ⋮ Approximating Weighted Completion Time for Order Scheduling with Setup Times ⋮ Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Empowering the configuration-IP: new PTAS results for scheduling with setup times

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• 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
• 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

This page was built for publication: