Zobrazeno 1 - 10
of 148
pro vyhledávání: '"Böckenhauer, Hans-Joachim"'
Autor:
Böckenhauer, Hans-Joachim, Gehnen, Matthias, Hromkovič, Juraj, Klasing, Ralf, Komm, Dennis, Lotze, Henri, Mock, Daniel, Rossmanith, Peter, Stocker, Moritz
We analyze the competitive ratio and the advice complexity of the online unbounded knapsack problem. An instance is given as a sequence of n items with a size and a value each, and an algorithm has to decide how often to pack each item into a knapsac
Externí odkaz:
http://arxiv.org/abs/2407.02045
We study a very restrictive graph exploration problem. In our model, an agent without persistent memory is placed on a vertex of a graph and only sees the adjacent vertices. The goal is to visit every vertex of the graph, return to the start vertex,
Externí odkaz:
http://arxiv.org/abs/2301.13860
We analyze the Disjoint Path Allocation problem (DPA) in the priority framework. Motivated by the problem of traffic regulation in communication networks, DPA consists of allocating edge-disjoint paths in a graph. While online algorithms for DPA have
Externí odkaz:
http://arxiv.org/abs/2202.10254
Autor:
Boeckenhauer, Hans-Joachim, Burjons, Elisabet, Frei, Fabian, Hromkovic, Juraj, Lotze, Henri, Rossmanith, Peter
In the online simple knapsack problem items are presented in an iterative fashion and an algorithm has to decide for each item whether to reject or permanently include it into the knapsack without any knowledge about the rest of the instance. The goa
Externí odkaz:
http://arxiv.org/abs/2009.14043
In the knapsack problem, we are given a knapsack of some capacity and a set of items, each with a size and a value. The goal is to pack a selection of these items fitting the knapsack that maximizes the total value. The online version of this problem
Externí odkaz:
http://arxiv.org/abs/2005.01867
Parameterized complexity allows us to analyze the time complexity of problems with respect to a natural parameter depending on the problem. Reoptimization looks for solutions or approximations for problem instances when given solutions to neighboring
Externí odkaz:
http://arxiv.org/abs/1809.10578
Moving an autonomous agent through an unknown environment is one of the crucial problems for robotics and network analysis. Therefore, it received a lot of attention in the last decades and was analyzed in many different settings. The graph explorati
Externí odkaz:
http://arxiv.org/abs/1804.06675
Publikováno v:
In Information and Computation November 2022 289 Part A
In this paper, we consider the problem of exploring unknown environments with autonomous agents. We model the environment as a graph with edge weights and analyze the task of visiting all vertices of the graph at least once. The hardness of this task
Externí odkaz:
http://arxiv.org/abs/1611.00934