Sacha Krug

dblp:25/10763 · DBLP profile ↗
← Back
9ranked-venue papers
1as first author
1since 2021 · last 2021
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 7 · 1 since 2021Applied, interdisciplinary, general and emerging computing · 2 · 1 first-author
YearPublicationVenuePosition
2021 On the advice complexity of the online dominating set problem
abstract
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 vertex, together with edges to all previously revealed vertices. Advice complexity is a framework to measure the amount of information an online algorithm is lacking. Here, an online algorithm reads advice bits from an infinite binary tape prepared beforehand by an all-knowing oracle. The advice complexity is the total number of advice bits read during the computation. Besides giving some insight into what makes an online problem hard, advice complexity can also be used as a means for proving lower bounds on the competitive ratio achievable by randomized online algorithms. We analyze the advice complexity of the online dominating set problem. For general graphs, we show tight upper and lower bounds for optimality. Then, we use a result for c-competitiveness to prove that no randomized online algorithm can be better than n1−ε-competitive, for any ε>0. Finally, we analyze the advice complexity of various graph classes for optimality.
Hans-Joachim Böckenhauer, Juraj Hromkovic, Sacha Krug, Walter Unger
Theor. Comput. Sci.3
2017 Improved analysis of the online set cover problem with advice
Stefan Dobrev, Jeff Edmonds, Dennis Komm, Rastislav Kralovic, Richard Královic, Sacha Krug, Tobias Mömke
Theor. Comput. Sci.6
2015 On Energy-Efficient Computations With Advice
Hans-Joachim Böckenhauer, Richard J. B. Dobson, Sacha Krug, Kathleen Steinhöfel
COCOON3
2014 On the Power of Advice and Randomization for the Disjoint Path Allocation Problem
Kfir Barhum, Hans-Joachim Böckenhauer, Michal Forisek, Heidi Gebauer, Juraj Hromkovic, Sacha Krug, Jasmin Smula, Björn Steffen
SOFSEM6
2014 On the advice complexity of the online L(2, 1)-coloring problem on paths and cycles
Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovic, Sacha Krug, Björn Steffen
Theor. Comput. Sci.4
2014 The string guessing problem as a method to prove lower bounds on the advice complexity
Hans-Joachim Böckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock
Theor. Comput. Sci.4
2013 On the Advice Complexity of the Online L(2, 1)-Coloring Problem on Paths and Cycles
Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovic, Sacha Krug, Björn Steffen
COCOON4
2013 The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity
Hans-Joachim Böckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock
COCOON4
2012 On the Approximation Ratio of the Path Matching Christofides Algorithm
Sacha Krug
SOFSEM1