Recent developments in the Theory of pre-processing

Michael Fellows

Abstract

Although pre-processing is a practical computing strategy almost universally employed for real-world attacks on NP-hard problems, it is perhaps surprising that for more than thirty years there has been no mathematically-disciplined theory of the subject. The parameterized/multivariate view of computational complexity makes such a theory possible, and this turns out to be deeply productive and useful. In the theory of parameterized complexity and algorithmics, the subject is termed kernelization. We survey the origins, recent developments and applications of the theory of polynomial-time kernelization. � 2011 Springer-Verlag.

Original language	English
Number of pages	2
Publication status	Published - 2011
Event	Joint Conference of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM 2011) - Berlin, Germany, Berlin, Germany Duration: 28 May 2011 → 31 May 2011 Conference number: 2011

Conference

Conference	Joint Conference of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM 2011)
Abbreviated title	FAW AAIM
Country/Territory	Germany
City	Berlin
Period	28/05/11 → 31/05/11

Cite this

@conference{2561d3e032d44caabdcb23d936b69bc1,

title = "Recent developments in the Theory of pre-processing",

abstract = "Although pre-processing is a practical computing strategy almost universally employed for real-world attacks on NP-hard problems, it is perhaps surprising that for more than thirty years there has been no mathematically-disciplined theory of the subject. The parameterized/multivariate view of computational complexity makes such a theory possible, and this turns out to be deeply productive and useful. In the theory of parameterized complexity and algorithmics, the subject is termed kernelization. We survey the origins, recent developments and applications of the theory of polynomial-time kernelization. � 2011 Springer-Verlag.",

keywords = "Algorithmics, Kernelization, NP-HARD problem, Parameterized, Parameterized complexity, Polynomial-time, Practical computing, Pre-processing, Real-world attack, Algorithms, Computational complexity",

author = "Michael Fellows",

year = "2011",

language = "English",

note = "Joint Conference of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM 2011), FAW AAIM ; Conference date: 28-05-2011 Through 31-05-2011",

}

TY - CONF

T1 - Recent developments in the Theory of pre-processing

AU - Fellows, Michael

N1 - Conference code: 2011

PY - 2011

Y1 - 2011

N2 - Although pre-processing is a practical computing strategy almost universally employed for real-world attacks on NP-hard problems, it is perhaps surprising that for more than thirty years there has been no mathematically-disciplined theory of the subject. The parameterized/multivariate view of computational complexity makes such a theory possible, and this turns out to be deeply productive and useful. In the theory of parameterized complexity and algorithmics, the subject is termed kernelization. We survey the origins, recent developments and applications of the theory of polynomial-time kernelization. � 2011 Springer-Verlag.

AB - Although pre-processing is a practical computing strategy almost universally employed for real-world attacks on NP-hard problems, it is perhaps surprising that for more than thirty years there has been no mathematically-disciplined theory of the subject. The parameterized/multivariate view of computational complexity makes such a theory possible, and this turns out to be deeply productive and useful. In the theory of parameterized complexity and algorithmics, the subject is termed kernelization. We survey the origins, recent developments and applications of the theory of polynomial-time kernelization. � 2011 Springer-Verlag.

KW - Algorithmics

KW - Kernelization

KW - NP-HARD problem

KW - Parameterized

KW - Parameterized complexity

KW - Polynomial-time

KW - Practical computing

KW - Pre-processing

KW - Real-world attack

KW - Algorithms

KW - Computational complexity

M3 - Abstract

T2 - Joint Conference of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM 2011)

Y2 - 28 May 2011 through 31 May 2011

ER -

Recent developments in the Theory of pre-processing

Abstract

Conference

Fingerprint

Cite this