{"id":"arxiv/2601.11841","url":"https://arxiv.org/abs/2601.11841","tags":["cs.DS","math.CO","math.PR"],"score":0,"title":"Analysis of a Random Local Search Algorithm for Dominating Set","domain":"cs.DS","source":"arxiv","authors":["Hendrik Higl"],"reviews":0,"subject":"cs.DS","summary":"Dominating Set is a well-known combinatorial optimization problem which finds application in computational biology or mobile communication. Because of its $\\mathrm{NP}$-hardness, one often turns to heuristics for good solutions. Many such heuristics have been empirically tested and perform rather well. However, it is not well understood why their results are so good or even what guarantees they can offer regarding their runtime or the quality of their results. For this, a strong theoretical foundation has to be established. We contribute to this by rigorously analyzing a Random Local Search…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-17","reactions":{}}