Marvin Künnemann

activity

20162025

most citedThe Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs

1 citations · 1 across the 3 of their papers we have counts for

collaborators

Showing cs.DSShow all

2 papers · 1 filter

cs.DS2023

The Effect of Sparsity on $k$ -Dominating Set and Related First-Order Graph Properties

Nick Fischer, Marvin Künnemann, Mirza Redzic

We revisit $k$ -Dominating Set, one of the first problems for which a tight $n^{k} - o (1)$ conditional lower bound (for $k \geq 3$ ), based on SETH, was shown (Pătraşcu and Williams, SODA…

cs.DS2023

Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise

Marvin Künnemann, Bodo Manthey, Rianne Veenstra

The 2-opt heuristic is a very simple local search heuristic for the traveling salesperson problem. In practice it usually converges quickly to solutions within a few percentages of…

The Effect of Sparsity on k-Dominating Set and Related First-Order Graph Properties

Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise

The Effect of Sparsity on $k$ -Dominating Set and Related First-Order Graph Properties