Simon Weber

collaborators

2 papers

cs.CC2025

Query-Efficient Fixpoints of $ℓ_{p}$ -Contractions

Sebastian Haslebacher, Jonas Lill, Patrick Schnider +1

We prove that an $ε$ -approximate fixpoint of a map $f : [0, 1]^{d} \to [0, 1]^{d}$ can be found with $O (d^{2} (lo g \frac{1}{ε} + lo g \frac{1}{1 - λ}))$ queries to $f$ if $f$ is $…

cs.DS2024

Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound

Jonas Lill, Kalina Petrova, Simon Weber

MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdős bound states that any connected graph on n vertice…

Query-Efficient Fixpoints of ℓp​-Contractions

Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound

Query-Efficient Fixpoints of $ℓ_{p}$ -Contractions