Scheduling and fixed-parameter tractability

Matthias Mnich, Andreas Wiese

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations


Fixed-parameter tractability analysis and scheduling are two core domains of combinatorial optimization which led to deep understanding of many important algorithmic questions. However, even though fixed-parameter algorithms are appealing for many reasons, no such algorithms are known for many fundamental scheduling problems. In this paper we present the first fixed-parameter algorithms for classical scheduling problems such as makespan minimization, scheduling with job-dependent cost functions - one important example being weighted flow time - and scheduling with rejection. To this end, we identify crucial parameters that determine the problems' complexity. In particular, we manage to cope with the problem complexity stemming from numeric input values, such as job processing times, which is usually a core bottleneck in the design of fixed-parameter algorithms. We complement our algorithms with W[1]-hardness results showing that for smaller sets of parameters the respective problems do not allow FPT-algorithms. In particular, our positive and negative results for scheduling with rejection explore a research direction proposed by Dániel Marx.

Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783319075563
StatePublished - 2014
Externally publishedYes
Event17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014 - Bonn, Germany
Duration: 23 Jun 201425 Jun 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8494 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014


Dive into the research topics of 'Scheduling and fixed-parameter tractability'. Together they form a unique fingerprint.

Cite this