On the advice complexity of the online dominating set problem

Autor: Walter Unger, Juraj Hromkovič, Hans-Joachim Böckenhauer, Sacha Krug

Publikováno v: Theoretical Computer Science, 862
Theoretical computer science 862, 81-96 (2021). doi:10.1016/j.tcs.2021.01.022 special issue: "A Fascinating Rainbow of Computation – Honoring Gheorghe Păun on the Occasion of His 70th Birthday / Edited by Lila Kari, Grzegorz Rozenberg, Arto Salomaa, Ion Petre"

A dominating set S of a graph is a set of vertices such that each vertex is in S or has a neighbor in S. The goal of the dominating set problem is to find such a set of minimum cardinality. In the online setting, the graph is revealed vertex by verte

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b80a7329a105324e8662af86085cd318
https://hdl.handle.net/20.500.11850/471612

Analysis of a near-metric TSP approximation algorithm

Autor: Sacha Krug

Publikováno v: RAIRO - Theoretical Informatics and Applications. 47:293-314

The traveling salesman problem (TSP) is one of the most fundamental optimization problems. We consider the β-metric traveling salesman problem (Δβ-TSP), i.e., the TSP restricted to graphs satisfying the β-triangle inequality c({v,w}) ≤ β(c({v,

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::9986825e4785e125af645d6ac9f6d1e0
https://doi.org/10.1051/ita/2013040

The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity

Autor: Sacha Krug, Dennis Komm, Juraj Hromkovič, Jasmin Smula, Andreas Sprock, Hans-Joachim Böckenhauer

Publikováno v: Lecture Notes in Computer Science ISBN: 9783642387678
COCOON

The advice complexity of an online problem describes the additional information both necessary and sufficient for online algorithms to compute solutions of a certain quality. In this model, an oracle inspects the input before it is processed by an on

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::01c7c7425abe28e8c9dec0ff79b2f0e0
https://doi.org/10.1007/978-3-642-38768-5_44

On the Approximation Ratio of the Path Matching Christofides Algorithm

Autor: Sacha Krug

Publikováno v: SOFSEM 2012: Theory and Practice of Computer Science ISBN: 9783642276590
SOFSEM

The traveling salesman problem (TSP) is one of the most fundamental optimization problems. We consider the β -metric traveling salesman problem (Δβ -TSP), i.e., the TSP restricted to graphs satisfying the β -triangle inequality c ({v ,w })≤β (

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::6ff1b759f5e4876597dc8c0ac83dbd49
https://doi.org/10.1007/978-3-642-27660-6_29