Sacha Krug

Publication Activity (10 Years)

Years Active: 2012-2021
Publications (10 Years): 2

Top Topics

Approximation Ratio

Efficient Computation

Top Venues

Theor. Comput. Sci.

RAIRO Theor. Informatics Appl.

Publications

Hans-Joachim Böckenhauer, Juraj Hromkovic, Sacha Krug, Walter Unger
On the advice complexity of the online dominating set problem. Theor. Comput. Sci. 862 (2021)
Stefan Dobrev, Jeff Edmonds, Dennis Komm, Rastislav Královic, Richard Královic, Sacha Krug, Tobias Mömke
Improved analysis of the online set cover problem with advice. Theor. Comput. Sci. 689 (2017)
Hans-Joachim Böckenhauer, Richard J. B. Dobson, Sacha Krug, Kathleen Steinhöfel
On Energy-Efficient Computations With Advice. COCOON (2015)
Sacha Krug
Towards using the history in online computation with advice. RAIRO Theor. Informatics Appl. 49 (2) (2015)
Hans-Joachim Böckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock
The string guessing problem as a method to prove lower bounds on the advice complexity. Theor. Comput. Sci. 554 (2014)
Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovic, Sacha Krug, Björn Steffen
On the advice complexity of the online L(2, 1)-coloring problem on paths and cycles. Theor. Comput. Sci. 554 (2014)
Kfir Barhum, Hans-Joachim Böckenhauer, Michal Forisek, Heidi Gebauer, Juraj Hromkovic, Sacha Krug, Jasmin Smula, Björn Steffen
On the Power of Advice and Randomization for the Disjoint Path Allocation Problem. SOFSEM (2014)
Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovic, Sacha Krug, Björn Steffen
(2, 1)-Coloring Problem on Paths and Cycles. COCOON (2013)
Sacha Krug
Analysis of a near-metric TSP approximation algorithm. RAIRO Theor. Informatics Appl. 47 (3) (2013)
Hans-Joachim Böckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock
The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity. COCOON (2013)
Sacha Krug
On the Approximation Ratio of the Path Matching Christofides Algorithm. SOFSEM (2012)
Hans-Joachim Böckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock
The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity. Electron. Colloquium Comput. Complex. 19 (2012)