TY  - JOUR
A1  - Quinzan, Francesco
A1  - Göbel, Andreas
A1  - Wagner, Markus
A1  - Friedrich, Tobias
T1  - Evolutionary algorithms and submodular functions
BT  - benefits of heavy-tailed mutations
JF  - Natural computing : an innovative journal bridging biosciences and computer sciences ; an international journal
N2  - A core operator of evolutionary algorithms (EAs) is the mutation. Recently, much attention has been devoted to the study of mutation operators with dynamic and non-uniform mutation rates. Following up on this area of work, we propose a new mutation operator and analyze its performance on the (1 + 1) Evolutionary Algorithm (EA). Our analyses show that this mutation operator competes with pre-existing ones, when used by the (1 + 1) EA on classes of problems for which results on the other mutation operators are available. We show that the (1 + 1) EA using our mutation operator finds a (1/3)-approximation ratio on any non-negative submodular function in polynomial time. We also consider the problem of maximizing a symmetric submodular function under a single matroid constraint and show that the (1 + 1) EA using our operator finds a (1/3)-approximation within polynomial time. This performance matches that of combinatorial local search algorithms specifically designed to solve these problems and outperforms them with constant probability. Finally, we evaluate the performance of the (1 + 1) EA using our operator experimentally by considering two applications: (a) the maximum directed cut problem on real-world graphs of different origins, with up to 6.6 million vertices and 56 million edges and (b) the symmetric mutual information problem using a four month period air pollution data set. In comparison with uniform mutation and a recently proposed dynamic scheme, our operator comes out on top on these instances.
KW  - Evolutionary algorithms
KW  - Mutation operators
KW  - Submodular functions
KW  - Matroids
Y1  - 2021
U6  - https://doi.org/10.1007/s11047-021-09841-7
SN  - 1572-9796
VL  - 20
IS  - 3
SP  - 561
EP  - 575
PB  - Springer Science + Business Media B.V.
CY  - Dordrecht
ER  - 
TY  - JOUR
A1  - Blaesius, Thomas
A1  - Friedrich, Tobias
A1  - Schirneck, Friedrich Martin
T1  - The complexity of dependency detection and discovery in relational databases
JF  - Theoretical computer science
N2  - Multi-column dependencies in relational databases come associated with two different computational tasks. The detection problem is to decide whether a dependency of a certain type and size holds in a given database, the discovery problem asks to enumerate all valid dependencies of that type. We settle the complexity of both of these problems for unique column combinations (UCCs), functional dependencies (FDs), and inclusion dependencies (INDs). We show that the detection of UCCs and FDs is W[2]-complete when parameterized by the solution size. The discovery of inclusion-wise minimal UCCs is proven to be equivalent under parsimonious reductions to the transversal hypergraph problem of enumerating the minimal hitting sets of a hypergraph. The discovery of FDs is equivalent to the simultaneous enumeration of the hitting sets of multiple input hypergraphs. We further identify the detection of INDs as one of the first natural W[3]-complete problems. The discovery of maximal INDs is shown to be equivalent to enumerating the maximal satisfying assignments of antimonotone, 3-normalized Boolean formulas.
KW  - data profiling
KW  - enumeration complexity
KW  - functional dependency
KW  - inclusion
KW  - dependency
KW  - parameterized complexity
KW  - parsimonious reduction
KW  - transversal hypergraph
KW  - Unique column combination
KW  - W[3]-completeness
Y1  - 2021
U6  - https://doi.org/10.1016/j.tcs.2021.11.020
SN  - 0304-3975
SN  - 1879-2294
VL  - 900
SP  - 79
EP  - 96
PB  - Elsevier
CY  - Amsterdam
ER  -