Evangelos Bampas

International journals

Andreas Bärtschi, Evangelos Bampas, Jérémie Chalopin, Shantanu Das, Christina Karousatou, and Matúš Mihalák:
Near-gathering of energy-constrained mobile agents. Theoretical Computer Science 849, 35-46 (2021). [doi] [elsevier] abstract Abstract: We study the task of gathering k energy-constrained mobile agents in an undirected edge-weighted graph. Each agent is initially placed on an arbitrary node and has a limited amount of energy, which constrains the distance it can move. Since this may render gathering at a single point impossible, we study three variants of near-gathering:
The goal is to move the agents into a configuration that minimizes either (i) the radius of a ball containing all agents, (ii) the maximum distance between any two agents, or (iii) the average distance between the agents. We prove that (i) is polynomial-time solvable, (ii) has a polynomial-time 2-approximation with a matching NP-hardness lower bound, while (iii) admits a polynomial-time 2(1-1/k)-approximation, but no FPTAS, unless P=NP. We extend some of our results to additive approximation.

Evangelos Bampas, Jurek Czyzowicz, David Ilcinkas, and Ralf Klasing:
Beachcombing on strips and islands. Theoretical Computer Science 806, 236-255 (2020). [doi] [elsevier] [accepted manuscript] abstract Abstract: A group of mobile robots (beachcombers) have to search collectively every point of a given domain. At any given moment, each robot can be in walking mode or in searching mode. It is assumed that each robot's maximum allowed searching speed is strictly smaller than its maximum allowed walking speed. A point of the domain is searched if at least one of the robots visits it in searching mode. The Beachcombers' Problem consists in developing efficient schedules (algorithms) for the robots which collectively search all the points of the given domain as fast as possible. We consider searching schedules in the following one-dimensional geometric domains: the cycle of a known circumference L, the finite straight line segment of a known length L, and the semi-infinite line [0,+∞].
We first consider the online Beachcombers' Problem (i.e. the scenario when the robots do not know in advance the length of the segment to be searched), where the robots are initially collocated at the origin of a semi-infinite line. It is sought to design a schedule A with maximum speed S, defined as S=inf_ℓ(ℓ ⁄ t_A(ℓ)), where t_A(ℓ) denotes the time when the search of the segment [0,ℓ] is completed under A. We consider a discrete and a continuous version of the problem, depending on whether the infimum is taken over ℓ∈ℕ^* or ℓ≥1. We prove that the LeapFrog algorithm, which was proposed in [Czyzowicz et al., SIROCCO 2014, LNCS 8576, pp. 23–36 (2014)], is in fact optimal in the discrete case. This settles in the affirmative a conjecture from that paper. We also show how to extend this result to the more general continuous online setting.
For the offline version of the Beachcombers' Problem (i.e. the scenario when the robots know in advance the length of the segment to be searched), we consider the t-source Beachcombers' Problem (i.e. all robots start from a fixed number of starting positions) on the cycle and on the finite segment. For the t-source Beachcombers' Problem on the cycle, we show that the structure of the optimal solutions is identical to the structure of the optimal solutions to the 2t-source Beachcombers' Problem on a finite segment. In consequence, by using results from [Czyzowicz et al., ALGOSENSORS 2014, LNCS 8847, pp. 3–21 (2014)], we prove that the 1-source Beachcombers' Problem on the cycle is NP-hard, and we derive approximation algorithms for the problem. For the t-source variant of the Beachcombers' Problem on the cycle and on the finite segment, we also derive efficient approximation algorithms.
One important contribution of our work is that, in all variants of the offline Beachcombers' Problem that we discuss, we allow the robots to change direction of movement and search points of the domain on both sides of their respective starting positions. This represents a significant generalization compared to the model considered in [Czyzowicz et al., ALGOSENSORS 2014, LNCS 8847, pp. 3–21 (2014)], in which each robot had a fixed direction of movement that was specified as part of the solution to the problem. We manage to prove that changes of direction do not help the robots achieve optimality.

Evangelos Bampas, Lélia Blin, Jurek Czyzowicz, David Ilcinkas, Arnaud Labourel, Maria Potop-Butucaru, and Sébastien Tixeuil:
On asynchronous rendezvous in general graphs. Theoretical Computer Science 753, 80-90 (2019). [doi] [elsevier] [accepted manuscript] abstract Abstract: A pair of agents (robots) are moving in a graph with the goal of meeting at the same node or while traversing the same edge. An asynchronous adversary knows the prescribed walks of the two agents and is in complete control of the speed of each agent during its walk. We provide a complete characterization of pairs of walks that enforce rendezvous against an asynchronous adversary after traversing a given number of edges. The characterization is efficient in that it can be checked in polynomial time. We argue that the certificate of rendezvous enforcement that is produced by the checking algorithm contains a wealth of information on why rendezvous is enforced.

Evangelos Bampas, Jurek Czyzowicz, Leszek Gąsieniec, David Ilcinkas, Ralf Klasing, Tomasz Kociumaka, and Dominik Pająk:
Linear search by a pair of distinct-speed robots. Algorithmica 81(1), 317-342 (2019). [doi] [springer] [open access pdf] abstract Abstract: Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. The search is completed when both robots arrive at the target point. The target is discovered at the moment when either robot arrives at its position. The robot knowing the placement of the target may communicate it to the other robot. We look for the algorithm with the shortest possible search time (i.e. the worst-case time at which both robots meet at the target) measured as a function of the target distance from the origin (i.e. the time required to travel directly from the starting point to the target at unit velocity).
We consider two standard models of communication between the robots, namely wireless communication and communication by meeting. In the case of communication by meeting, a robot learns about the target while sharing the same location with a robot possessing this knowledge. We propose here an optimal search strategy for two robots including the respective lower bound argument, for the full spectrum of their maximal speeds. This extends the main result of Chrobak et al. (SOFSEM 2015) referring to the exact complexity of the problem for the case when the speed of the slower robot is at least one third of the faster one. In the wireless communication model, a message sent by one robot is instantly received by the other robot, regardless of their current positions on the line. For this model, we design a strategy which is optimal whenever the faster robot is at most $\sqrt{17} + 4 \approx 8.123$ times faster than the slower one. We also prove that otherwise the wireless communication offers no advantage over communication by meeting.

Evangelos Bampas, Christina Karousatou, Aris Pagourtzis, and Katerina Potika:
Minimum multiplicity edge coloring via orientation. Discrete Applied Mathematics 247, 380-388 (2018). [doi] [elsevier] [accepted manuscript] abstract Abstract: We study an edge coloring problem in multigraphs, in which each node incurs a cost equal to the number of appearances of the most frequent color among those received by its incident edges. We seek an edge coloring with a given number w of colors, that minimizes the total cost incurred by the nodes of the multigraph. We consider a class of approximation algorithms for this problem, which are based on orienting the edges of the multigraph, then grouping appropriately the incoming and outgoing edges at each node so as to construct a bipartite multigraph of maximum degree w, and finally obtaining a proper edge coloring of this bipartite multigraph. As shown by Nomikos et al. (Inform. Process. Lett. 80 (2001) 249-256), simply choosing an arbitrary edge orientation in the first step yields a 2-approximation algorithm. We investigate whether this approximation ratio can be improved by a more careful choice of the edge orientation in the first step. We prove that, assuming a worst-case bipartite edge coloring, this is not possible in the asymptotic sense, as there exists a family of instances in which any orientation gives a solution with cost at least $2−\Theta(\frac{1}{w})$ times the optimal. On the positive side, we show how to produce an orientation which results in a solution with cost within a factor of $2-\frac{1}{2^w}$ of the optimal, thus yielding an approximation ratio strictly better than 2. This improvement is important in view of the fact that this graph-theoretic problem models, among others, wavelength assignment to communication requests in multifiber optical star networks. In this context, the parameter w corresponds to the number of available wavelengths per fiber, which is limited in practice due to technological constraints.

Evangelos Bampas and David Ilcinkas:
On mobile agent verifiable problems. Information and Computation 260, 51-71 (2018). [doi] [elsevier] [accepted manuscript] abstract Abstract: We consider decision problems that are solved in a distributed fashion by synchronous mobile agents operating in an unknown, anonymous network. Each agent has a unique identifier and an input string and they have to decide collectively a property which may involve their input strings, the graph on which they are operating, and their particular starting positions. Building on recent work by Fraigniaud and Pelc [J. Parallel Distrib. Comput., vol. 109, pp. 117-128], we introduce several natural new computability classes allowing for a finer classification of problems below MAV or its complement class co-MAV, the former being the class of problems that are verifiable when the agents are provided with an appropriate certificate. We provide inclusion and separation results among all these classes. We also determine their closure properties with respect to set-theoretic operations. Our main technical tool, which is of independent interest, is a new meta-protocol that enables the execution of a possibly infinite number of mobile agent protocols essentially in parallel, similarly to the well-known dovetailing technique from classical computability theory.

Evangelos Bampas, Christina Karousatou, Aris Pagourtzis, and Katerina Potika:
Path multicoloring in spider graphs with even color multiplicity. Information Processing Letters 133, 1-4 (2018). [doi] [elsevier] [accepted manuscript] abstract Abstract: We give an exact polynomial-time algorithm for the problem of coloring a collection of paths defined on a spider graph using a minimum number of colors (Min-PMC), while respecting a given even maximum admissible color multiplicity on each edge. This complements a previous result on the complexity of Min-PMC in spider graphs, where it was shown that, for every odd k, the problem is NP-hard in spiders with admissible color multiplicity k on each edge. We also obtain an exact polynomial-time algorithm for maximizing the number of colored paths with a given number of colors (Max-PMC) in spider graphs with even admissible color multiplicity on each edge.

Evangelos Bampas, Leszek Gąsieniec, Nicolas Hanusse, David Ilcinkas, Ralf Klasing, Adrian Kosowski, and Tomasz Radzik:
Robustness of the rotor-router mechanism. Algorithmica 78(3), 869-895 (2017). [doi] [springer] [accepted manuscript] abstract Abstract: The rotor-router model, also called the Propp machine, was first considered as a deterministic alternative to the random walk. The edges adjacent to each node v (or equivalently, the exit ports at v) are arranged in a fixed cyclic order, which does not change during the exploration. Each node v maintains a port pointer π_v which indicates the exit port to be adopted by an agent on the conclusion of the next visit to this node (the “next exit port”). The rotor-router mechanism guarantees that after each consecutive visit at the same node, the pointer at this node is moved to the next port in the cyclic order. It is known that, in an undirected graph G with m edges, the route adopted by an agent controlled by the rotor-router mechanism eventually forms an Euler tour based on arcs obtained via replacing each edge in G by two arcs with opposite direction. The process of ushering the agent to an Euler tour is referred to as the lock-in problem. In [Yanovski et al., Algorithmica 37(3), 165–186 (2003)], it was proved that, independently of the initial configuration of the rotor-router mechanism in G, the agent locks-in in time bounded by 2mD, where D is the diameter of G.
In this paper we examine the dependence of the lock-in time on the initial configuration of the rotor-router mechanism. Our analysis is performed in the form of a game between a player P intending to lock-in the agent in an Euler tour as quickly as possible and its adversary A with the counter objective. We consider all cases of who decides the initial cyclic orders and the initial values π_v. We show, for example, that if A provides its own port numbering after the initial setup of pointers by P, the worst-case complexity of the lock-in problem is $\Theta(m \cdot \min\{\log m, D\})$. We also investigate the robustness of the rotor-router graph exploration in presence of faults in the pointers π_v or dynamic changes in the graph. We show, for example, that after the exploration establishes an Eulerian cycle, if k edges are added to the graph, then a new Eulerian cycle is established within O(km) steps.

Evangelos Bampas, Andreas-Nikolas Göbel, Aris Pagourtzis, and Aris Tentes:
On the connection between interval size functions and path counting. Computational Complexity 26(2), 421-467 (2017). [doi] [springer] [accepted manuscript] abstract Abstract: We investigate the complexity of hard (#P-complete) counting problems that have easy decision version. By “easy decision,” we mean that deciding whether the result of counting is non-zero is in P. This property is shared by several well-known problems, such as counting the number of perfect matchings in a given graph or counting the number of satisfying assignments of a given DNF formula. We focus on classes of such hard-to-count easy-to-decide problems which emerged through two seemingly disparate approaches: one taken by Hemaspaandra et al. (2007, SIAM J. Comput. 36(5), 1264–1300), who defined classes of functions that count the size of intervals of ordered strings, and one followed by Kiayias et al. (2001, Lect. Notes Comput. Sc. 2563, 453–463), who defined the class TotP, consisting of functions that count the total number of paths of NP computations. We provide inclusion and separation relations between TotP and interval size counting classes, by means of new classes that we define in this work. Our results imply that many known #P-complete problems with easy decision are contained in the classes defined by Hemaspaandra et al, but are unlikely to be complete for these classes under reductions under which these classes are downward closed, e.g. parsimonious reductions. This, applied to the #MonSat problem, partially answers an open question of Hemaspaandra et al. We also define a new class of interval size functions which strictly contains FP and is strictly contained in TotP under reasonable complexity-theoretic assumptions. We show that this new class contains hard counting problems.

Evangelos Bampas, Nikos Leonardos, Euripides Markou, Aris Pagourtzis, and Matoula Petrolia:
Improved Periodic Data Retrieval in asynchronous rings with a faulty host. Theoretical Computer Science 608, 231-254 (2015). [doi] [elsevier] [accepted manuscript] abstract Abstract: The exploration problem has been extensively studied in unsafe networks containing malicious hosts of a highly harmful nature, called black holes, which completely destroy mobile agents that visit them. In a recent work, Královič and Miklík (SIROCCO 2010, LNCS 6058, pp. 157–167) considered various types of malicious host behavior in the context of the Periodic Data Retrieval problem in asynchronous ring networks with exactly one malicious host. In this problem, a team of initially co-located agents must report data from all safe nodes of the network to the homebase, infinitely often. The malicious host can choose whether to kill visiting agents or allow them to pass through (gray hole). In another variation of the model, the malicious host can, in addition, alter its whiteboard contents in order to deceive visiting agents. The goal is to design a protocol for Periodic Data Retrieval using as few agents as possible.
In this paper, we present the first nontrivial lower bounds on the number of agents for Periodic Data Retrieval in asynchronous ring networks. Specifically, we show that at least 4 agents are needed when the malicious host is a gray hole, and at least 5 agents are needed when the malicious host whiteboard is unreliable. This improves the previous lower bound of 3 in both cases and answers an open question posed in the aforementioned paper.
On the positive side, we propose an optimal protocol for Periodic Data Retrieval in asynchronous rings with a gray hole, which solves the problem with only 4 agents. This improves the previous upper bound of 9 agents and settles the question of the optimal number of agents in the gray-hole case. Finally, we propose a protocol with 7 agents when the whiteboard of the malicious host is unreliable, significantly improving the previously known upper bound of 27 agents. Along the way, we set forth a detailed framework for studying networks with malicious hosts of varying capabilities.

Evangelos Bampas, Davide Bilò, Guido Drovandi, Luciano Gualà, Ralf Klasing, and Guido Proietti:
Network verification via routing table queries. Journal of Computer and System Sciences 81(1), 234-248 (2015). [doi] [elsevier] [accepted manuscript] abstract Abstract: The network verification problem is that of establishing the accuracy of a high-level description of its physical topology, by making as few measurements as possible on its nodes. This task can be formalized as an optimization problem that, given a graph and a query model specifying the information returned by a query at a node, asks for finding a minimum-size subset of nodes to be queried so as to univocally identify the graph. This problem has been studied with respect to different query models, assuming that a node had some global knowledge about the network. Here, we propose a new query model based on the local knowledge a node instead usually has. Quite naturally, we assume that a query at a given node returns the associated routing table, i.e., a set of entries which provides, for each destination node, a corresponding (set of) first-hop node(s) along an underlying shortest path.
Highlights:
  • Any network of n nodes needs Ω(log⁡log⁡n) queries to be verified.
  • Constant diameter networks need Ω(log⁡n) queries.
  • There is no o(log⁡n)-approximation algorithm for diameter 2 networks, unless P=NP.
  • We give an O(log⁡n)-approximation algorithm for diameter 2 networks.
  • We give exact linear-time algorithms for paths, trees, and cycles of even length.

Evangelos Bampas, Aris Pagourtzis, George Pierrakos, and Katerina Potika:
On a noncooperative model for wavelength assignment in multifiber optical networks. IEEE/ACM Transactions on Networking 20(4), 1125-1137 (2012). [doi] [ieee] [accepted manuscript] abstract Abstract: We propose and investigate Selfish Path MultiColoring games as a natural model for noncooperative wavelength assignment in multifiber optical networks. In this setting, we view the wavelength assignment process as a strategic game in which each communication request selfishly chooses a wavelength in an effort to minimize the maximum congestion that it encounters on the chosen wavelength. We measure the cost of a certain wavelength assignment as the maximum, among all physical links, number of parallel fibers employed by this assignment. We start by settling questions related to the existence and computation of and convergence to pure Nash equilibria in these games. Our main contribution is a thorough analysis of the price of anarchy of such games, that is, the worst-case ratio between the cost of a Nash equilibrium and the optimal cost. We first provide upper bounds on the price of anarchy for games defined on general network topologies. Along the way, we obtain an upper bound of 2 for games defined on star networks. We next show that our bounds are tight even in the case of tree networks of maximum degree 3, leading to nonconstant price of anarchy for such topologies. In contrast, for network topologies of maximum degree 2, the quality of the solutions obtained by selfish wavelength assignment is much more satisfactory: We prove that the price of anarchy is bounded by 4 for a large class of practically interesting games defined on ring networks.

Evangelos Bampas, Aris Pagourtzis, and Katerina Potika:
An experimental study of maximum profit wavelength assignment in WDM rings. Networks 57(3), 285-293 (2011). [doi] [wiley] [accepted manuscript] abstract Abstract: We are interested in the problem of satisfying a maximum-profit subset of undirected communication requests in an optical ring that uses the Wavelength Division Multiplexing technology. We present four deterministic and purely combinatorial algorithms for this problem, and give theoretical guarantees for their worst-case approximation ratios. Two of these algorithms are novel, whereas the rest are adaptation of earlier approaches. An experimental evaluation of the algorithms in terms of attained profit and execution time reveals that the theoretically best algorithm performs only marginally better than one of the new algorithms, while at the same time being several orders of magnitude slower. Furthermore, an extremely fast greedy heuristic with nonconstant approximation ratio performs reasonably well and may be favored over the other algorithms whenever it is crucial to minimize execution time.

International conferences

Andreas Bärtschi, Evangelos Bampas, Jérémie Chalopin, Shantanu Das, Christina Karousatou, and Matúš Mihalák:
Near-gathering of energy-constrained mobile agents. In Proceedings of SIROCCO 2019 - 26th International Colloquium on Structural Information and Communication Complexity, Lecture Notes in Computer Science, vol. 11639, Springer, 2019, pp. 52-65. [doi] [springer] abstract Abstract: We study the task of gathering k energy-constrained mobile agents in an undirected edge-weighted graph. Each agent is initially placed on an arbitrary node and has a limited amount of energy, which constrains the distance it can move. Since this may render gathering at a single point impossible, we study three variants of near-gathering: The goal is to move the agents into a configuration that minimizes either (i) the radius of a ball containing all agents, (ii) the maximum distance between any two agents, or (iii) the average distance between the agents. We prove that (i) is polynomial-time solvable, (ii) has a polynomial-time 2-approximation with a matching NP-hardness lower bound, while (iii) admits a polynomial-time 2(1 − 1 ⁄ k)-approximation, but no FPTAS, unless P=NP. We extend some of our results to additive approximation.

Evangelos Bampas, Shantanu Das, Dariusz Dereniowski, and Christina Karousatou:
Collaborative delivery by energy-sharing low-power mobile robots. In Proceedings of ALGOSENSORS 2017 - 13th International Symposium on Algorithms and Experiments for Wireless Networks, Lecture Notes in Computer Science, vol. 10718, Springer, 2017, pp. 1-12. [doi] [springer] [draft] abstract Abstract: We study two variants of delivery problems for mobile robots sharing energy. Each mobile robot can store at any given moment at most two units of energy, and whenever two robots are at the same location, they can transfer energy between each other, respecting the maximum capacity. The robots operate in a simple graph and initially each robot has two units of energy. A single edge traversal by an robot reduces its energy by one unit and the robot can only perform such move initially having at least one unit of energy. There are two distinguished nodes s and t in the graph and the goal for the robots is to deliver the package initially present on s to the node t. The package can be passed from one robot to another when they are colocated. In the first problem we study, the robots are initially placed at some given nodes of the graph and the question is whether the delivery is feasible. We prove that this problem is NP-complete. In the second problem, the initial positions of the robots are not fixed but a subset of nodes H of the graph is given as input together with an integer k, and the question is as follows: is there a placement of k robots at nodes in H such that the delivery is possible? We prove that this problem can be solved in polynomial time.

Evangelos Bampas, Jurek Czyzowicz, Leszek Gąsieniec, David Ilcinkas, Ralf Klasing, Tomasz Kociumaka, and Dominik Pająk:
Linear search by a pair of distinct-speed robots. In Proceedings of SIROCCO 2016 - 23rd International Colloquium on Structural Information and Communication Complexity, Lecture Notes in Computer Science, vol. 9988, Springer, 2016, pp. 195-211. [doi] [springer] [preproceedings] abstract Abstract: Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. The search is completed when both robots arrive at the target point. The target is discovered at the moment when either robot arrives at its position. The robot knowing the placement of the target may communicate it to the other robot. We look for the algorithm with the shortest possible search time (i.e. the worst-case time at which both robots meet at the target) measured as a function of the target distance from the origin (i.e. the time required to travel directly from the starting point to the target at unit velocity).
We consider two standard models of communication between the robots, namely wireless communication and communication by meeting. In the case of communication by meeting, a robot learns about the target while sharing the same location with the robot possessing this knowledge. We propose here an optimal search strategy for two robots including the respective lower bound argument, for the full spectrum of their maximal speeds. This extends the main result from [Chrobak et al., SOFSEM 2015, LNCS 8939, pp. 164-176 (2015)] referring to the exact complexity of the problem for the case when the speed of the slower robot is at least one third of the faster one. In addition, we consider also the wireless communication model, in which a message sent by one robot is instantly received by the other robot, regardless of their current positions on the line. In this model, we design an optimal strategy whenever the faster robot is at most 6 times faster than the slower one.

Evangelos Bampas and David Ilcinkas:
On mobile agent verifiable problems. In Proceedings of LATIN 2016 - 12th Latin American Theoretical Informatics Symposium, Lecture Notes in Computer Science, vol. 9644, Springer, 2016, pp. 123-137. [doi] [springer] [draft] abstract Abstract: We consider decision problems that are solved in a distributed fashion by synchronous mobile agents operating in an unknown, anonymous network. Each agent has a unique identifier and an input string and they have to decide collectively a property which may involve their input strings, the graph on which they are operating, and their particular starting positions. Building on recent work by Fraigniaud and Pelc [LATIN 2012, LNCS 7256, pp. 362–374], we introduce several natural new computability classes allowing for a finer classification of problems below co-MAV or MAV, the latter being the class of problems that are verifiable when the agents are provided with an appropriate certificate. We provide inclusion and separation results among all these classes. We also determine their closure properties with respect to set-theoretic operations. Our main technical tool, which is of independent interest, is a new meta-protocol that enables the execution of a possibly infinite number of mobile agent protocols essentially in parallel, similarly to the well-known dovetailing technique from classical computability theory.

Evangelos Bampas, Jurek Czyzowicz, David Ilcinkas, and Ralf Klasing:
Beachcombing on strips and islands. In Proceedings of ALGOSENSORS 2015 - 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, Lecture Notes in Computer Science, vol. 9536, Springer, 2016, pp. 155-168. [doi] [springer] [draft] abstract Abstract: A group of mobile robots (beachcombers) have to search collectively every point of a given domain. At any given moment, each robot can be in walking mode or in searching mode. It is assumed that each robot's maximum allowed searching speed is strictly smaller than its maximum allowed walking speed. A point of the domain is searched if at least one of the robots visits it in searching mode. The Beachcombers' Problem consists in developing efficient schedules (algorithms) for the robots which collectively search all the points of the given domain as fast as possible.
We first consider the online Beachcombers' Problem, where the robots are initially collocated at the origin of a semi-infinite line. It is sought to design a schedule A with maximum speed S, defined as $S=\inf_\ell\frac{\ell}{t_A(\ell)$, where $t_A(\ell)$ denotes the time when the search of the segment $[0,\ell]$ is completed under A. We consider a discrete and a continuous version of the problem, depending on whether the infimum is taken over $\ell\in\mathbb{N}^\star$ or $\ell\geq 1$. We prove that the LeapFrog algorithm, which was proposed in [Czyzowicz et al., SIROCCO 2014, LNCS 8576, pp. 23–36 (2014)], is in fact optimal in the discrete case. This settles in the affirmative a conjecture from that paper. We also show how to extend this result to the more general continuous online setting.
For the offline version of the Beachcombers' Problem, we consider the single-source Beachcombers' Problem on the cycle, as well as the multi-source Beachcombers' Problem on the cycle and on the finite segment. For the single-source Beachcombers' Problem on the cycle, we show that the structure of the optimal solutions is identical to the structure of the optimal solutions to the two-source Beachcombers' Problem on a finite segment. In consequence, by using results from [Czyzowicz et al., ALGOSENSORS 2014, LNCS 8847, pp. 3–21 (2014)], we prove that the single-source Beachcombers' Problem on the cycle is NP-hard, and we derive approximation algorithms for the problem. For the multi-source variant of the Beachcombers' Problem on the cycle and on the finite segment, we obtain efficient approximation algorithms.
One important contribution of our work is that, in all variants of the offline Beachcombers' Problem that we discuss, we allow the robots to change direction of movement and search points of the domain on both sides of their respective starting positions. This represents a significant generalization compared to the model considered in [Czyzowicz et al., ALGOSENSORS 2014, LNCS 8847, pp. 3–21 (2014)], in which each robot had a fixed direction of movement that was specified as part of the solution to the problem. We manage to prove that changes of direction do not help the robots achieve optimality.

Evangelos Bampas, Christina Karousatou, Aris Pagourtzis, and Katerina Potika:
Scheduling connections via path and edge multicoloring. In Proceedings of ADHOC-NOW 2015 - 14th International Conference on Ad-Hoc Networks and Wireless, Lecture Notes in Computer Science, vol. 9143, Springer, 2015, pp. 33-47. [doi] [springer] [draft] abstract Abstract: We consider path multicoloring problems, in which one is given a collection of paths defined on a graph and is asked to color some or all of them so as to optimize certain objective functions. Typical objectives are: (a) the minimization of the average, over all edges, of the maximum-multiplicity color when the number of colors is given (MinAvgMult-PMC), (b) the minimization of the number of colors when the maximum multiplicity for each edge is given (Min-PMC), or (c) the maximization of the number of colored paths when both the number of colors and a maximum multiplicity constraint for each edge are given (Max-PMC). Such problems also capture edge multicoloring variants (such as MinAvgMult-EMC, Min-EMC, and Max-EMC) as special cases and find numerous applications in resource allocation, most notably in optical and wireless networks, and in communication task scheduling.
Our contribution is two-fold: On the one hand, we give an exact polynomial-time algorithm for Min-PMC on spider networks with even admissible color multiplicities on each edge. On the other hand, we present an approximation algorithm for MinAvgMult-PMC in star networks, with a ratio strictly better than 2; our algorithm uses an appropriate path orientation. We also show that any algorithm which is based on path orientation cannot achieve an approximation ratio better than 7/6. Our results apply to the corresponding edge multicoloring problems as well.

Evangelos Bampas, Nikos Leonardos, Euripides Markou, Aris Pagourtzis, and Matoula Petrolia:
Improved Periodic Data Retrieval in asynchronous rings with a faulty host. In Proceedings of SIROCCO 2014 - 21st International Colloquium on Structural Information and Communication Complexity, Lecture Notes in Computer Science, vol. 8576, Springer, 2014, pp. 355-370. [doi] [springer] [draft] abstract Abstract: The exploration problem has been extensively studied in unsafe networks containing malicious hosts of a highly harmful nature, called black holes, which completely destroy mobile agents that visit them. In a recent work, Královič and Miklík [SIROCCO 2010, LNCS 6058, pp. 157–167] considered various types of malicious host behavior in the context of the Periodic Data Retrieval problem in asynchronous ring networks with exactly one malicious host. In this problem, a team of initially co-located agents must report data from all safe nodes of the network to the homebase, infinitely often. The malicious host can choose whether to kill visiting agents or allow them to pass through (gray hole). In another variation of the model, the malicious host can, in addition, alter its whiteboard contents in order to deceive visiting agents. The goal is to design a protocol for Periodic Data Retrieval using as few agents as possible.
In this paper, we present the first nontrivial lower bounds on the number of agents for Periodic Data Retrieval in asynchronous ring networks. Specifically, we show that at least 4 agents are needed when the malicious host is a gray hole, and at least 5 agents are needed when the malicious host whiteboard is unreliable. This improves the previous lower bound of 3 in both cases and answers an open question posed in the aforementioned paper.
On the positive side, we propose an optimal protocol for Periodic Data Retrieval in asynchronous rings with a gray hole, which solves the problem with only 4 agents. This improves the previous upper bound of 9 agents and settles the question of the optimal number of agents in the gray-hole case. Finally, we propose a protocol with 7 agents when the whiteboard of the malicious host is unreliable, significantly improving the previously known upper bound of 27 agents. Along the way, we set forth a detailed framework for studying networks with malicious hosts of varying capabilities.

Evangelos Bampas, Anissa Lamani, Franck Petit, and Mathieu Valero:
Self-stabilizing balancing algorithm for containment-based trees. In Proceedings of SSS 2013 - 15th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Lecture Notes in Computer Science, vol. 8255, Springer, 2013, pp. 191-205. [doi] [springer] [arxiv] abstract Abstract: Containment-based trees are widely used to build data indexes, range-queryable overlays, publish/subscribe systems both in centralized and distributed contexts. In addition to their versatility, their balanced shape ensures an overall satisfactory performance. Recently, it has been shown that their distributed implementations can be fault-resilient. However, this robustness is achieved at the cost of unbalancing the structure. While the structure remains correct in terms of searchability, its performance can be significantly decreased. In this paper, we propose a distributed self-stabilizing algorithm to balance containment-based trees.

Evangelos Bampas, Aris Pagourtzis, George Pierrakos, and Vasilis Syrgkanis:
Selfish resource allocation in optical networks. In Proceedings of CIAC 2013 - 8th International Conference on Algorithms and Complexity, Lecture Notes in Computer Science, vol. 7878, Springer, 2013, pp. 25-36. [doi] [springer] [draft] abstract Abstract: We introduce Colored Resource Allocation Games as a new model for selfish routing and wavelength assignment in multifiber all-optical networks. Colored Resource Allocation Games are a generalization of congestion and bottleneck games where players have their strategies in multiple copies (colors). We focus on two main subclasses of these games depending on the player cost: in Colored Congestion Games the player cost is the sum of latencies of the resources allocated to the player, while in Colored Bottleneck Games the player cost is the maximum of these latencies. We investigate the pure price of anarchy for three different social cost functions and prove tight bounds for each separate case. We first consider a social cost function which is particularly meaningful in the setting of multifiber all-optical networks, where it captures the objective of fiber cost minimization. Additionally, we consider the two usual social cost functions (maximum and average player cost) and obtain improved bounds that could not have been derived using earlier results for the standard models for congestion and bottleneck games.

Evangelos Bampas, Davide Bilò, Guido Drovandi, Luciano Gualà, Ralf Klasing, and Guido Proietti:
Network verification via routing table queries. In Proceedings of SIROCCO 2011 - 18th International Colloquium on Structural Information and Communication Complexity, Lecture Notes in Computer Science, vol. 6796, Springer, 2011, pp. 270-281. [doi] [springer] [draft] abstract Abstract: We address the problem of verifying the accuracy of a map of a network by making as few measurements as possible on its nodes. This task can be formalized as an optimization problem that, given a graph G=(V,E), and a query model specifying the information returned by a query at a node, asks for finding a minimum-size subset of nodes of G to be queried so as to univocally identify G. This problem has been faced w.r.t. a couple of query models assuming that a node had some global knowledge about the network. Here, we propose a new query model based on the local knowledge a node instead usually has. Quite naturally, we assume that a query at a given node returns the associated routing table, i.e., a set of entries which provides, for each destination node, a corresponding (set of) first-hop node(s) along an underlying shortest path. First, we show that any network of n nodes needs Ω(loglogn) queries to be verified. Then, we prove that there is no o(logn)-approximation algorithm for the problem, unless P=NP, even for networks of diameter 2. On the positive side, we provide an O(logn)-approximation algorithm to verify a network of diameter 2, and we give exact polynomial-time algorithms for paths, trees, and cycles of even length.

Evangelos Bampas, Jurek Czyzowicz, Leszek Gąsieniec, David Ilcinkas, and Arnaud Labourel:
Almost optimal asynchronous rendezvous in infinite multidimensional grids. In Proceedings of DISC 2010 - 24th International Symposium on Distributed Computing, Lecture Notes in Computer Science, vol. 6343, Springer, 2010, pp. 297-311. [doi] [springer] [draft] abstract Abstract: Two anonymous mobile agents (robots) moving in an asynchronous manner have to meet in an infinite grid of dimension δ>0, starting from two arbitrary positions at distance at most d. Since the problem is clearly infeasible in such general setting, we assume that the grid is embedded in a δ-dimensional Euclidean space and that each agent knows the Cartesian coordinates of its own initial position (but not the one of the other agent). We design an algorithm permitting the agents to meet after traversing a trajectory of length O(d^δ polylogd). This bound for the case of 2d-grids subsumes the main result of [ICALP 2010, LNCS 6199, pp. 502–514]. The algorithm is almost optimal, since the Ω(d^δ) lower bound is straightforward.
Further, we apply our rendezvous method to the following network design problem. The ports of the δ-dimensional grid have to be set such that two anonymous agents starting at distance at most d from each other will always meet, moving in an asynchronous manner, after traversing a O(d^δ polylogd) length trajectory.
We can also apply our method to a version of the geometric rendezvous problem. Two anonymous agents move asynchronously in the δ-dimensional Euclidean space. The agents have the radii of visibility of r₁ and r₂, respectively. Each agent knows only its own initial position and its own radius of visibility. The agents meet when one agent is visible to the other one. We propose an algorithm designing the trajectory of each agent, so that they always meet after traveling a total distance of O((d/r)^δ polylog(d/r)), where r=min(r₁, r₂) and for r≥1.

Evangelos Bampas, Leszek Gąsieniec, Ralf Klasing, Adrian Kosowski, and Tomasz Radzik:
Robustness of the rotor-router mechanism. In Proceedings of OPODIS 2009 - 13th International Conference on Principles of Distributed Systems, Lecture Notes in Computer Science, vol. 5923, Springer, 2009, pp. 345-358. [doi] [springer] [draft] abstract Abstract: We consider the model of exploration of an undirected graph G by a single agent which is called the rotor-router mechanism or the Propp machine (among other names). Let π_v indicate the edge adjacent to a node v which the agent took on its last exit from v. The next time when the agent enters node v, first a "rotor" at node v advances pointer π_v to the edge next(π_v) which is next after the edge π_v in a fixed cyclic order of the edges adjacent to v. Then the agent is directed onto edge π_v to move to the next node. It was shown before that after initial O(mD) steps, the agent periodically follows one established Eulerian cycle, that is, in each period of 2m consecutive steps the agent traverses each edge exactly twice, once in each direction. The parameters m and D are the number of edges in G and the diameter of G. We investigate robustness of such exploration in presence of faults in the pointers π_v or dynamic changes in the graph. We show that after the exploration establishes an Eulerian cycle,
  • if at some step the values of k pointers π_v are arbitrarily changed, then a new Eulerian cycle is established within O(km) steps;
  • if at some step k edges are added to the graph, then a new Eulerian cycle is established within O(km) steps;
  • if at some step an edge is deleted from the graph, then a new Eulerian cycle is established within O(γm) steps, where γ is the smallest number of edges in a cycle in graph G containing the deleted edge.
Our proofs are based on the relation between Eulerian cycles and spanning trees known as the "BEST" Theorem (after de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte).

Evangelos Bampas, Leszek Gąsieniec, Nicolas Hanusse, David Ilcinkas, Ralf Klasing, and Adrian Kosowski:
Euler tour lock-in problem in the rotor-router model (I choose pointers and you choose port numbers). In Proceedings of DISC 2009 - 23rd International Symposium on Distributed Computing, Lecture Notes in Computer Science, vol. 5805, Springer, 2009, pp. 423-435. [doi] [springer] [hal]

Evangelos Bampas, Aris Pagourtzis, George Pierrakos, and Vasilis Syrgkanis:
Colored resource allocation games (extended abstract). In Proceedings of CTW 2009 - 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, École Polytechnique and CNAM, 2009, pp. 68-72. [lix]

Evangelos Bampas, Andreas-Nikolas Göbel, Aris Pagourtzis, and Aris Tentes:
On the connection between interval size functions and path counting. In Proceedings of TAMC 2009 - 6th Annual Conference on Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol. 5532, Springer, 2009, pp. 108-117. [doi] [springer] [draft]

Evangelos Bampas, Aris Pagourtzis, George Pierrakos, and Katerina Potika:
On a non-cooperative model for wavelength assignment in multifiber optical networks. In Proceedings of ISAAC 2008 - 19th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, vol. 5369, Springer, 2008, pp. 159-170. [doi] [springer] [draft]

Evangelos Bampas, Aris Pagourtzis, and Katerina Potika:
Maximum profit wavelength assignment in WDM rings (extended abstract). In Proceedings of CTW 2008 - 7th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, University of Milan, 2008, pp. 35-38. [unimi]

Evangelos Bampas, Georgia Kaouri, Michael Lampis, and Aris Pagourtzis:
Periodic Metro Scheduling. In Proceedings of ATMOS 2006 - 6th Workshop on Algorithmic Methods and Models for Optimization of Railways, OpenAccess Series in Informatics, vol. 5, Schloss Dagstuhl, 2006. [doi] [dagstuhl]

International conferences (abstract)

Evangelos Bampas, Aris Pagourtzis, George Pierrakos, and Katerina Potika:
Selfish wavelength assignment in multifiber optical networks (abstract). In Proceedings of AAAC 2008 - 1st annual meeting of the Asian Association for Algorithms and Computation.

National conferences

Evangelos Bampas, Aris Pagourtzis, and Katerina Potika:
Maximum request satisfaction in WDM rings: Algorithms and experiments. In Proceedings of PCI 2007 - 11th Panhellenic Conference on Informatics, Current Trends in Informatics, vol. A, New Technologies Publications, 2007, pp. 627-642. [upatras]

National conferences (abstract)

Evangelos Bampas, Jérémie Chalopin, Shantanu Das, Jan Hackfeld, and Christina Karousatou:
Comment explorer un arbre inconnu avec des agents à énergie limitée ? (Maximal exploration of trees with energy-constrained agents) In Proceedings of AlgoTel 2017 - 19èmes Rencontres Francophones pour les Aspects Algorithmiques des Télécommunications, HAL, 2017, hal-01523302. [hal]

Evangelos Bampas and David Ilcinkas:
Problèmes vérifiables par agents mobiles. (On mobile agent verifiable problems) In Proceedings of AlgoTel 2015 - 17èmes Rencontres Francophones pour les Aspects Algorithmiques des Télécommunications, HAL, 2015, hal-01148475. [hal]

Theses

Evangelos Bampas:
Routing and wavelength assignment in optical networks. Ph.D. dissertation, School of Electrical and Computer Engineering, National Technical University of Athens, 2009 (main text in English). Available as Ph.D. Dissertation PD2009-0055 on the Artemis gray literature server. [artemis] [local copy]

Evangelos Bampas:
Algorithmic techniques in complexity theory. Diploma thesis, School of Electrical and Computer Engineering, National Technical University of Athens, 2004 (in Greek). Available as Diploma Thesis DT2004-0171 on the Artemis gray literature server. [artemis] [local copy]

Locally stored copies of the above papers are provided for the purpose of fast dissemination of scholarly work on a non-commercial basis only. Where applicable, all copyrights are withheld by the respective publishers.

Co-authors

Andreas Bärtschi, Davide Bilò, Lélia Blin, Jérémie Chalopin, Jurek Czyzowicz, Shantanu Das, Dariusz Dereniowski, Guido Drovandi, Leszek Gąsieniec, Andreas-Nikolas Göbel, Luciano Gualà, Jan Hackfeld, Nicolas Hanusse, David Ilcinkas, Georgia Kaouri, Christina Karousatou, Ralf Klasing, Tomasz Kociumaka, Adrian Kosowski, Arnaud Labourel, Anissa Lamani, Michael Lampis, Nikos Leonardos, Euripides Markou, Matúš Mihalák, Aris Pagourtzis, Dominik Pająk, Matoula Petrolia, Franck Petit, George Pierrakos, Katerina Potika, Maria Potop-Butucaru, Guido Proietti, Tomasz Radzik, Vasilis Syrgkanis, Aris Tentes, Sébastien Tixeuil, Mathieu Valero.