Scheduling meets \(n\)-fold integer programming
From MaRDI portal
Publication:2317129
DOI10.1007/s10951-017-0550-0zbMath1418.90113arXiv1603.02611OpenAlexW3103589466WikidataQ62044465 ScholiaQ62044465MaRDI QIDQ2317129
Publication date: 8 August 2019
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1603.02611
Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items (27)
New algorithms for minimizing the weighted number of tardy jobs on a single machine ⋮ About the Complexity of Two-Stage Stochastic IPs ⋮ A general scheme for solving a large set of scheduling problems with rejection in FPT time ⋮ Integer programming in parameterized complexity: five miniatures ⋮ High-multiplicity \(N\)-fold IP via configuration LP ⋮ Block-structured integer programming: can we parameterize without the largest coefficient? ⋮ A multivariate complexity analysis of the material consumption scheduling problem ⋮ Unnamed Item ⋮ On the complexity of scheduling problems with a fixed number of parallel identical machines ⋮ Structural parameters for scheduling with assignment restrictions ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding ⋮ Integer Programming in Parameterized Complexity: Three Miniatures. ⋮ Fixed-Parameter Approximation Schemes for Weighted Flowtime. ⋮ The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints ⋮ On the parameterized tractability of single machine scheduling with rejection ⋮ Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized complexity of a coupled-task scheduling problem ⋮ Improved approximation algorithms for two-stage flowshops scheduling problem ⋮ Unnamed Item ⋮ An EPTAS for scheduling on unrelated machines of few different types ⋮ Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting ⋮ 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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The third comprehensive survey on scheduling problems with setup times/costs
- Fundamentals of parameterized complexity
- Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
- Interval scheduling and colorful independent sets
- Scheduling and fixed-parameter tractability
- Nonlinear discrete optimization. An algorithmic theory
- On the parametric complexity of schedules to minimize tardy tasks.
- \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling]
- Bin packing with fixed number of bins revisited
- A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity \(2^{O(n\log n)}\)
- \(n\)-fold integer programming in cubic time
- Integer optimization on convex semialgebraic sets
- Graver basis and proximity techniques for block-structured separable convex integer minimization problems
- A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
- A complete 4-parametric complexity classification of short shop scheduling problems
- Integer Programming with a Fixed Number of Variables
- Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
- Fifty years of scheduling: a survey of milestones
- Huge Unimodular $n$-Fold Programs
- Strip Graphs: Recognition and Scheduling
- Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler
- Scheduling independent tasks to reduce mean finishing time
- Semidefinite Optimization and Convex Algebraic Geometry
- Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs
- Technical Note—Minimizing Average Flow Time with Parallel Machines
- Complexity of preemptive minsum scheduling on unrelated parallel machines
- Completing Partial Schedules for Open Shop with Unit Processing Times and Routing
- Convex separable optimization is not much harder than linear optimization
This page was built for publication: Scheduling meets \(n\)-fold integer programming
