The string guessing problem as a method to prove lower bounds on the advice complexity

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

Publikováno v: In Theoretical Computer Science 16 October 2014 554:95-108

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Analysis of approximation algorithms for the traveling salesman problem in near-metric graphs

Autor: Krug, Sacha

We consider the beta-metric traveling salesman problem (Delta-beta-TSP), i.e., the TSP restricted to input instances satisfying the beta-triangle inequality c({v,w})

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::3b29cc483d597a5a7444c483b7fbea44

On Energy-Efficient Computations With Advice.

Autor: Böckenhauer, Hans-Joachim, Dobson, Richard, Krug, Sacha, Steinhöfel, Kathleen

Publikováno v: Computing & Combinatorics: 21st International Conference, COCOON 2015, Beijing, China, August 4-6, 2015, Proceedings; 2015, p747-758, 12p

On the Power of Advice and Randomization for the Disjoint Path Allocation Problem.

Autor: Barhum, Kfir, Böckenhauer, Hans-Joachim, Forišek, Michal, Gebauer, Heidi, Hromkovič, Juraj, Krug, Sacha, Smula, Jasmin, Steffen, Björn

Publikováno v: SOFSEM 2014: Theory & Practice of Computer Science; 2014, p89-101, 13p