A5038261463- Optimization and Search Problems
- Auction Theory and Applications
- Complexity and Algorithms in Graphs
- Vehicle Routing Optimization Methods
- Mobile Agent-Based Network Management
- Distributed systems and fault tolerance
- Blockchain Technology Applications and Security
- Advanced Graph Theory Research
- Graph Theory and Algorithms
- Data Management and Algorithms
- Caching and Content Delivery
- Modular Robots and Swarm Intelligence
Humboldt-Universität zu Berlin
2017-2020
Institut für Hygiene und Umwelt
2018-2019
Technische Universität Berlin
2015-2018
Institute of Mathematics and Informatics
2016-2018
Czech Academy of Sciences, Institute of Mathematics
2016-2018
We study the problem of deterministically exploring an undirected and initially unknown graph with n vertices either by a single agent equipped set pebbles or collaborating agents. The are unlabeled cannot be distinguished agents, but edges incident to vertex have locally distinct labels. is explored when all been visited at least one agent. In this setting, it known that for without Θ(log ) bits memory necessary sufficient explore any most vertices. interested in how requirement decreases...
We consider the problem of delivering $m$ messages between specified source-target pairs in a weighted undirected graph, by $k$ mobile agents initially located at distinct nodes graph. Each agent consumes energy proportional to distance it travels graph and we are interested optimizing total consumption for team agents. Unlike previous related work, heterogeneous with different rates (weights~$w_i$). To solve delivery problem, face three major challenges: \emph{Collaboration} (how work...
We consider the online traveling salesperson problem (TSP), where requests appear over time on real line and need to be visited by a server initially located at origin. distinguish between closed open TSP, depending whether eventually needs return origin or not. While TSP is very natural that was introduced more than two decades ago, no tight competitive analysis known date. settle this providing bounds ratios for both variant of problem. In particular, we provide 1.64-competitive algorithm,...
We consider the online traveling salesperson problem (TSP), where requests appear over time on real line and need to be visited by a server initially located at origin. distinguish between closed open TSP, depending whether eventually needs return origin or not. While TSP is very natural that was introduced more than two decades ago, no tight competitive analysis known date. settle this providing bounds ratios for both variant of problem. In particular, we provide 1.64-competitive algorithm,...
We consider the fundamental problem of exploring an undirected and initially unknown graph by agent with little memory. The vertices are unlabeled, edges incident to a vertex have locally distinct labels. In this setting, it is known that Θ(log n) bits memory necessary sufficient explore any at most n vertices. show requirement can be decreased significantly making part distributable in form pebbles. A pebble device dropped mark collected when returns vertex. for O(log log distinguishable...
We consider the fundamental problem of exploring an undirected and initially unknown graph by agent with little memory. The vertices are unlabeled, edges incident to a vertex have locally distinct labels. In this setting, it is known that ⊝(log n) bits memory necessary sufficient explore any at most n vertices. show requirement can be decreased significantly making part distributable in form pebbles. A pebble device dropped mark collected when returns vertex. for ℴ(log log distinguishable...
We consider the online traveling salesperson problem (TSP), where requests appear over time on real line and need to be visited by a server initially located at origin. distinguish between closed open TSP, depending whether eventually needs return origin or not. While TSP is very natural that was introduced more than two decades ago, no tight competitive analysis known date. settle this providing bounds ratios for both variant of problem. In particular, we provide 1.64-competitive algorithm,...
We consider the problem of exploring an unknown tree with a team $k$ initially colocated mobile agents. Each agent has limited energy and cannot, as result, traverse more than $B$ edges. The goal is to maximize number nodes collectively visited by all agents during execution. Initially, have no knowledge about structure tree, but they gradually discover topology new assume that can communicate each other at arbitrary distances. Therefore obtained one after traversing edge instantaneously...
We present a general consensus framework that allows to easily introduce customizable Byzantine fault tolerant algorithm an existing (Delegated) Proof-of-Stake blockchain. prove the safety of protocol under assumption less than 1/3 validators are Byzantine. The further for participants choose subjective decision thresholds in order obtain even case larger proportion validators. Moreover, liveness is shown if crash. Based on framework, we Lisk-BFT, Lisk ecosystem. Lisk-BFT integrates with...
We study the problem of deterministically exploring an undirected and initially unknown graph with $n$ vertices either by a single agent equipped set pebbles, or collaborating agents. The are unlabeled cannot be distinguished agents, but edges incident to vertex have locally distinct labels. is explored when all been visited at least one agent. In this setting, it known that for without pebbles $\Theta(\log n)$ bits memory necessary sufficient explore any most vertices. interested in how...