Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 34 for “"Kernelization"”.
-
String to String Correction Kernelization
The StringToStringCorrection problem asks, given mutable string M, target string T, and positive integer k, can M be mutated into T using at most k operations (single symbol deletions or swaps of adjacent symbols) applied to M? The problem is known to be NP-complete. Abu-Khzam et al. give the first …
-
Clustering and Inconsistent Information: A Kernelization Approach
… and disjoint-FVS (a variation of FVS), from a kernelization approach. A kernelization algorithm in polynomial time reduces a problem instance provably to speed up the further processing with other approaches. For each of the problems studied, an efficient kernelization algorithm of linear or …
-
Kernelization and Enumeration: New Approaches to Solving Hard Problems
… to design efficient parameterized algorithms, kernelization. The motivation is that instances of small size are easier to solve. Roughly speaking, kernelization is a preprocess on the input instances and is able to significantly reduce their sizes. We present a 2k kernel for the cluster editing …
-
Crown Reductions and Decompositions: Theoretical Results and Practical Methods
<p>Two kernelization schemes for the vertex cover problem, an NP-hard problem in graph theory, are compared. The first, crown reduction, is based on the identification of a graph structure called a crown and is relatively new while the second, LP-kernelization has been used for some time. A proof …
-
Graph-Theoretical Tools for the Analysis of Complex Networks
… of fixed parameter tractability (branching and kernelization) is considered in the context of a parallel implementation of vertex cover. Results of testing on a wide variety of graphs derived from both real and synthetic data are presented. It is shown that the relative success of kernelization …
-
Cuts and Partitions in Graphs/Trees with Applications
… algorithms, approximation algorithms, and kernelization algorithms for these problems. For the maximum agreement forest problem, we proceed from the bottommost level of trees and extend solutions to whole trees. With this technique, we show that the maxi- mum agreement forest problem is …
-
Big Data Algorithms with Limited Local Resources
… that cover the the points of S, we present two kernelization algorithms: the first one is a randomized algorithm that runs in time O(n log k +k2(log2 k)(log log k)2) and space O(k2 log2 k), and computes a kernel of size at most k2 with probability at least 1 – 2 ; the other algorithm is …
-
Obstructions and algorithms for graph layouts problems
… interplay with parameterized complexity and kernelization.
-
A Performance Characterization of Kernel-Based Algorithms for Anomaly Detection in Hyperspectral Imagery
… derived from each of the linear methods using a kernelization process that involves nonlinearly mapping the data into a high-dimensional feature space and replacing all dot products with a kernel function using the kernel-trick. A projection separation statistic determines how anomalous each …
-
Robust Weighted Kernel Logistic Regression in Imbalanced and Rare Events Data
… regularization, approximate numerical methods, kernelization, bias correction, and efficient implementation, all of which enable RE-WKLR to be at once fast, accurate, and robust.
-
Person Re-identification Based on Kernel Local Fisher Discriminant Analysis and Mahalanobis Distance Learning
… [38] is used to reduce dimensionality given that kernelization method can greatly improve Re-ID performance for nonlinearity. Inspired by [47], an SPD matrix is then learned on lower-dimensional descriptors based on the limitation that the maximum intraclass distance is at least one unit smaller …
-
Diversity optimization and parameterized analysis of heuristic search methods for combinatorial optimization problems
… up to solve massive input instances. A parallel kernelization technique is proposed which is motivated by the assumption that huge graphs are composed of several easy to solve components while the overall problem is hard to solve. Using evolutionary algorithms to generate a diverse set of …
-
Structured and Interpretable Representations for Ensemble and Dynamical Systems
… and geometric optimal control. Second, a moment-kernelization framework is developed for studying ensemble systems, transforming infinite-dimensional parameterized dynamics into moment representations suitable for finite-dimensional approximation. This framework facilitates fundamental system …
-
Study on Two Optimization Problems: Line Cover and Maximum Genus Embedding
… the dual problem by applying approximation and kernelization, obtaining an approximation algorithm with ratio k - 1 and a kernel of size O(k^4). Then we survey related geometric properties on LCP. Finally we propose a Parameterized Algorithm to solve LCP with running time O*(k^k/1:35^k). We …
Page 1 of 2