Results 11 to 20 of about 1,405 (240)

(Meta) Kernelization [PDF]

open access: yesJournal of the ACM, 2009
In a parameterized problem, every instance I comes with a positive integer k . The problem is said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the instance I to a polynomial in k while preserving the answer ...
Bodlaender, Hans L.   +5 more
openaire   +12 more sources

Lossy kernelization [PDF]

open access: yesProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017
58 pages. Version 2 contain new results: PSAKS for Cycle Packing and approximate kernel lower bounds for Set Cover and Hitting Set parameterized by universe ...
Lokshtanov, D.   +3 more
openaire   +6 more sources

Propositional Kernels [PDF]

open access: yesEntropy, 2021
The pervasive presence of artificial intelligence (AI) in our everyday life has nourished the pursuit of explainable AI. Since the dawn of AI, logic has been widely used to express, in a human-friendly fashion, the internal process that led an (intelligent) system to deliver a specific output.
Mirko Polato, Fabio Aiolli
openaire   +3 more sources

Approximate Turing Kernelization and Lower Bounds for Domination Problems [PDF]

open access: yes, 2023
An α-approximate polynomial Turing kernelization is a polynomial-time algorithm that computes an (α c)-approximate solution for a parameterized optimization problem when given access to an oracle that can compute c-approximate solutions to instances with
Kratsch, Stefan, Kunz, Pascal
core   +3 more sources

On the Kernelization of Global Constraints [PDF]

open access: yes, 2017
Kernelization is a powerful concept from parameterized complexity theory that captures (a certain idea of) efficient polynomial-time preprocessing for hard decision problems.
Hébrard, Emmanuel   +3 more
core   +3 more sources

Kernel Treelets [PDF]

open access: yesAdvances in Data Science and Adaptive Analysis, 2019
A new method for hierarchical clustering of data points is presented. It combines treelets, a particular multiresolution decomposition of data, with a mapping on a reproducing kernel Hilbert space. The proposed approach, called kernel treelets (KT), uses this mapping to go from a hierarchical clustering over attributes (the natural output of treelets)
Hedi Xia, Héctor D. Ceniceros
openaire   +3 more sources

PACE 2021 Kernelization track

open access: yes, 2021
<p> These are the sources of the PaSTEC solver for the kernelization track of the PACE 2021 challenge.</p ...
Valentin Bartier   +5 more
core   +1 more source

Hierarchical Kernel and Sub-kernels [PDF]

open access: yesAmerican Review of Mathematics and Statistics, 2017
This paper shows the theoretical development of hierarchy by kernels and an algorithm used to obtain an interesting class or partition from a hierarchy. Also shown is the theorem about the Kernels Optimal Criterion and how it is expressed as a function of the masses of the points of the vector space and product scale points, the inertia of the cloud ...
openaire   +2 more sources

Bidimensionality and Kernels [PDF]

open access: yesSIAM Journal on Computing, 2010
Bidimensionality theory was introduced by [E. D. Demaine et al., J. ACM, 52 (2005), pp. 866--893] as a tool to obtain subexponential time parameterized algorithms on H-minor-free graphs. In [E. D. Demaine and M. Hajiaghayi, Bidimensionality: New connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on ...
Fomin, Fedor   +3 more
openaire   +7 more sources

Lossy Kernelization for (Implicit) Hitting Set Problems [PDF]

open access: yes, 2023
We re-visit the complexity of polynomial time pre-processing (kernelization) for the d-Hitting Set problem. This is one of the most classic problems in Parameterized Complexity by itself, and, furthermore, it encompasses several other of the most well ...
Lokshtanov, Daniel   +6 more
core   +1 more source

Home - About - Disclaimer - Privacy