Scheduling meets n-fold integer programming
From MaRDI portal
Scheduling meets \(n\)-fold integer programming
Abstract: Scheduling problems are fundamental in combinatorial optimization. Much work has been done on approximation algorithms for NP-hard cases, but relatively little is known about exact solutions when some part of the input is a fixed parameter. In 2014, Mnich and Wiese initiated a systematic study in this direction. In this paper we continue this study and show that several additional cases of fundamental scheduling problems are fixed parameter tractable for some natural parameters. Our main tool is n-fold integer programming, a recent variable dimension technique which we believe to be highly relevant for the parameterized complexity community. This paper serves to showcase and highlight this technique. Specifically, we show the following four scheduling problems to be fixed-parameter tractable, where p max is the maximum processing time of a job and w max is the maximum weight of a job: - Makespan minimization on uniformly related machines parameterized by , - Makespan minimization on unrelated machines parameterized by and the number of kinds of machines, - Sum of weighted completion times minimization on unrelated machines parameterized by and the number of kinds of machines, - The same problem, parameterized by the number of distinct job times and the number of machines.
Recommendations
Cites work
- \(n\)-fold integer programming in cubic time
- \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
- A complete 4-parametric complexity classification of short shop scheduling problems
- A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity \(2^{O(n\log n)}\)
- A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
- Algebraic and geometric ideas in the theory of discrete optimization
- Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
- Bin packing with fixed number of bins revisited
- Completing partial schedules for open shop with unit processing times and routing
- Complexity of preemptive minsum scheduling on unrelated parallel machines
- Convex separable optimization is not much harder than linear optimization
- Fifty years of scheduling: a survey of milestones
- Fundamentals of parameterized complexity
- Graver basis and proximity techniques for block-structured separable convex integer minimization problems
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Huge unimodular \(n\)-fold programs
- Integer optimization on convex semialgebraic sets
- Integer Programming with a Fixed Number of Variables
- Nonlinear discrete optimization. An algorithmic theory
- On the parametric complexity of schedules to minimize tardy tasks.
- Parameterized and approximation results for scheduling with a low rank processing time matrix
- Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
- Scheduling and fixed-parameter tractability
- Scheduling independent tasks to reduce mean finishing time
- Scheduling two competing agents when one agent has significantly fewer jobs
- Semidefinite Optimization and Convex Algebraic Geometry
- Strip Graphs: Recognition and Scheduling
- Technical Note—Minimizing Average Flow Time with Parallel Machines
- The third comprehensive survey on scheduling problems with setup times/costs
- Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler
- Voting and bribing in single-exponential time
Cited in
(51)- On the parameterized tractability of single machine scheduling with rejection
- Empowering the configuration-IP: new PTAS results for scheduling with setup times
- Moderate exponential-time algorithms for scheduling problems
- About the complexity of two-stage stochastic IPs
- A general scheme for solving a large set of scheduling problems with rejection in FPT time
- Combinatorial \(n\)-fold integer programming and applications
- The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
- Parameterized complexity of a coupled-task scheduling problem
- Improved approximation algorithms for two-stage flowshops scheduling problem
- Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
- Integer programming in parameterized complexity: five miniatures
- Block-structured integer programming: can we parameterize without the largest coefficient?
- Scheduling personal finances via integer programming
- Parameterized and approximation results for scheduling with a low rank processing time matrix
- Integer programming in parameterized complexity: three miniatures
- Fixed-parameter approximation schemes for weighted flowtime
- About the Complexity of Two-Stage Stochastic IPs
- Empowering the configuration-IP -- new PTAS results for scheduling with setups times
- Tight complexity lower bounds for integer linear programming with few constraints
- Combinatorial \(n\)-fold integer programming and applications
- Near-linear time algorithm for n-fold ILPs via color coding
- Scheduling and fixed-parameter tractability
- scientific article; zbMATH DE number 7651172 (Why is no real title available?)
- High-multiplicity \(N\)-fold IP via configuration LP
- Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
- A multivariate complexity analysis of the material consumption scheduling problem
- On the complexity of scheduling problems with a fixed number of parallel identical machines
- On the parameterized tractability of single machine scheduling with rejection to minimize the weighted makespan
- On the NP-hardness of two scheduling problems under linear constraints
- Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines
- FPT algorithms for a special block-structured integer program with applications in scheduling
- Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming
- Serial batching to minimize the weighted number of tardy jobs
- Robust scheduling on uniform machines. New results using a relaxed approximation guarantee
- (Near)-optimal algorithms for sparse separable convex integer programs
- Exact and approximate high-multiplicity scheduling on identical machines
- Parameterized algorithms for block-structured integer programs with large entries
- Integer points in the degree-sequence polytope
- Scheduling kernels via configuration LP
- Fairness in repetitive scheduling
- Complexity of scheduling few types of jobs on related and unrelated machines
- Collapsing the tower -- on the complexity of multistage stochastic IPs
- Tight lower bounds for block-structured integer programs
- Moderate exponential-time algorithms for scheduling problems
- Tight lower bounds for block-structured integer programs
- Additive approximation schemes for load balancing problems
- An EPTAS for minimizing the total weighted completion time of jobs with release dates on uniformly related machines
- An EPTAS for minimizing the total weighted completion time of jobs with release dates on uniformly related machines
- An efficient polynomial time approximation scheme for minimizing the total weighted completion time on uniformly related machines
- Exact and approximate algorithms for high-multiplicity scheduling with rejection on parallel machines
- New algorithms for minimizing the weighted number of tardy jobs on a single machine
This page was built for publication: Scheduling meets \(n\)-fold integer programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2317129)
