Sacha Krug

According to our database, Sacha Krug authored at least 10 papers between 2012 and 2021.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2021

On the advice complexity of the online dominating set problem.

Hans-Joachim Böckenhauer, Juraj Hromkovic, Sacha Krug, Walter Unger

Theor. Comput. Sci., 2021

2017

Improved analysis of the online set cover problem with advice.

Stefan Dobrev, Jeff Edmonds, Dennis Komm, Rastislav Královic, Richard Královic, Sacha Krug, Tobias Mömke

Theor. Comput. Sci., 2017

2015

Towards using the history in online computation with advice.

Sacha Krug

RAIRO Theor. Informatics Appl., 2015

On Energy-Efficient Computations With Advice.

Hans-Joachim Böckenhauer, Richard J. B. Dobson, Sacha Krug, Kathleen Steinhöfel

Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

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., 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., 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

Proceedings of the SOFSEM 2014: Theory and Practice of Computer Science, 2014

2013

Analysis of a near-metric TSP approximation algorithm.

Sacha Krug

RAIRO Theor. Informatics Appl., 2013

On the Advice Complexity of the Online <i>L</i>(2, 1)-Coloring Problem on Paths and Cycles.

Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovic, Sacha Krug, Björn Steffen

Proceedings of the Computing and Combinatorics, 19th International Conference, 2013

2012

On the Approximation Ratio of the Path Matching Christofides Algorithm.

Sacha Krug

Proceedings of the SOFSEM 2012: Theory and Practice of Computer Science, 2012