Abstract Machine scheduling problems are a long-time key domain of algorithms and
complexity research. A novel approach to machine scheduling problems are fixed …

The idea for this book was conceived over the second bottle of Villa Maria's Caber net
Medot'89, at the dinner of the Australasian Combinatorics Conference held at Palmerston …

Classical complexity theory analyzes and classifies problems by the amount of a resource,
usually time or space, that is required by algorithms solving them. It was a fundamental idea …

This handbook provides an up-to-date compendium of fundamental computer science
topics, techniques, and applications. Along with updating and revising many of the existing …

Approximation algorithms and parameterized complexity are usually considered to be two
separate ways of dealing with hard algorithmic problems. In this paper, our aim is to …

Parameterization and approximation are two popular ways of coping with NP-hard
problems. More recently, the two have also been combined to derive many interesting …

In this paper we give a programmatic overview of parameterized computational complexity
in the broad context of the problem of coping with computational intractability. We give some …

We demonstrate a new connection between fixed-parameter tractability and approximation
algorithms for combinatorial optimization problems on planar graphs and their …

What is this? Well its a PDF version of the website www. ComplexityZoo. com typeset in
LATEX using the complexity package. Well, what's that? The original Complexity Zoo is a …

We present an efficient polynomial time approximation scheme (EPTAS) for scheduling on
uniform processors, ie, finding a minimum length schedule for a set of n independent jobs on …