5 citations · 5 across the 1 of their papers we have counts for
6 papers
Evolutionary Diversity Optimisation in Constructing Satisfying Assignments
Adel Nikfarjam, Ralf Rothenberger, Frank Neumann +1
Computing diverse solutions for a given problem, in particular evolutionary diversity optimisation (EDO), is a hot research topic in the evolutionary computation community. This pa…
The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability
Thomas Bläsius, Tobias Friedrich, Andreas Göbel +2
Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms…
The Satisfiability Threshold for Non-Uniform Random 2-SAT
Tobias Friedrich, Ralf Rothenberger
Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. Its worst-case hardness lies at the core of computational complexity theory, for exa…
Greedy Maximization of Functions with Bounded Curvature under Partition Matroid Constraints
Tobias Friedrich, Andreas Göbel, Frank Neumann +2
We investigate the performance of a deterministic GREEDY algorithm for the problem of maximizing functions under a partition matroid constraint. We consider non-monotone submodular…
Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT
Tobias Friedrich, Anton Krohmer, Ralf Rothenberger +2
Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. The worst-case hardness of SAT lies at the core of computational complexity theory.…
Greed is Good for Deterministic Scale-Free Networks
Ankit Chauhan, Tobias Friedrich, Ralf Rothenberger
Large real-world networks typically follow a power-law degree distribution. To study such networks, numerous random graph models have been proposed. However, real-world networks ar…