Source author record

Ioannis Lamprou

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination

We consider the \emph{Budgeted} version of the classical \emph{Connected Dominating Set} problem (BCDS). Given a graph $G$ and a budget $k$ , we seek a connected subset of at most $k$ vertices maximizing the number of dominated vertices in $G$ . We improve over the previous $(1-1/e)/13$ approximation in [Khuller, Purohit, and Sarpatwar,\ \emph{SODA 2014}] by introducing a new method for performing tree decompositions in the analysis of the last part of the algorithm. This new approach provides a $(1-1/e)/12$ approximation guarantee. By generalizing the analysis of the first part of the algorithm, we are able to modify it appropriately and obtain a further improvement to $(1-e^{-7/8})/11$ . On the other hand, we prove a $(1-1/e+ε)$ inapproximability bound, for any $ε> 0$ . We also examine the \emph{edge-vertex domination} variant, where an edge dominates its endpoints and all vertices neighboring them. In \emph{Budgeted Edge-Vertex Domination} (BEVD), we are given a graph $G$ , and a budget $k$ , and we seek a, not necessarily connected, subset of $k$ edges such that the number of dominated vertices in $G$ is maximized. We prove there exists a $(1-1/e)$ -approximation algorithm. Also, for any $ε> 0$ , we present a $(1-1/e+ε)$ -inapproximability result by a gap-preserving reduction from the \emph{maximum coverage} problem. Finally, we examine the "dual" \emph{Partial Edge-Vertex Domination} (PEVD) problem, where a graph $G$ and a quota $n'$ are given. The goal is to select a minimum-size set of edges to dominate at least $n'$ vertices in $G$ . In this case, we present a $H(n')$ -approximation algorithm by a reduction to the \emph{partial cover} problem.

preprint2016arXiv

Fast Two-Robot Disk Evacuation with Wireless Communication

In the fast evacuation problem, we study the path planning problem for two robots who want to minimize the worst-case evacuation time on the unit disk. The robots are initially placed at the center of the disk. In order to evacuate, they need to reach an unknown point, the exit, on the boundary of the disk. Once one of the robots finds the exit, it will instantaneously notify the other agent, who will make a beeline to it. The problem has been studied for robots with the same speed~\cite{s1}. We study a more general case where one robot has speed $1$ and the other has speed $s \geq 1$ . We provide optimal evacuation strategies in the case that $s \geq c_{2.75} \approx 2.75$ by showing matching upper and lower bounds on the worst-case evacuation time. For $1\leq s < c_{2.75}$ , we show (non-matching) upper and lower bounds on the evacuation time with a ratio less than $1.22$ . Moreover, we demonstrate that a generalization of the two-robot search strategy from~\cite{s1} is outperformed by our proposed strategies for any $s \geq c_{1.71} \approx 1.71$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.