VZVassilis Zissimopoulos

Vassilis Zissimopoulos

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Vassilis Zissimopoulos has a total of 26 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Provably Efficient Resource Allocation of Cloud Native Functions For Network Services

    by Nikolaos Lazaropoulos, Ioannis Vaxevanakis, Ioannis Sigalas, Ioannis Lamprou, Vassilis Zissimopoulos

  • Calibrations scheduling with arbitrary lengths and activation length

    by Eric Angel, Evripidis Bampis, Vincent Chau, Vassilis Zissimopoulos


  • Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination

    by Ioannis Lamprou, Ioannis Sigalas, Vassilis Zissimopoulos

    We consider the Budgeted version of the classical 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, 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+\epsilon )\) inapproximability bound, for any \(\epsilon > 0\). We also examine the edge-vertex domination variant, where an edge dominates its endpoints and all vertices neighboring them. In 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 \(\epsilon > 0\), we present a \((1-1/e+\epsilon )\)-inapproximability result by a gap-preserving reduction from the maximum coverage problem. Finally, we examine the “dual” 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 partial cover problem.


  • Open Access

    Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination

    by Ioannis Lamprou, Ioannis Sigalas, Vassilis Zissimopoulos

    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+\epsilon)$ inapproximability bound, for any $\epsilon > 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 $\epsilon > 0$, we present a $(1-1/e+\epsilon)$-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.

  • Open Access

    Calibrations Scheduling Problem with Arbitrary Lengths and Activation Length

    by Eric Angel, Evripidis Bampis, Vincent Chau, Vassilis Zissimopoulos

    Bender et al. (SPAA 2013) have proposed a theoretical framework for testing in contexts where safety mistakes must be avoided. Testing in such a context is made by machines that need to be often calibrated. Given that calibration costs, it is important to study policies minimizing the calibration cost while performing all the necessary tests. We focus on the single-machine setting and we extend the model proposed by Bender et al. by considering that the jobs have arbitrary processing times and that the preemption of jobs is allowed. For this case, we propose an optimal polynomial time algorithm. Then, we study the case where there are several types of calibrations with different lengths and costs. We first prove that the problem becomes NP-hard for arbitrary processing times even when the preemption of the jobs is allowed. Finally, we focus on the case of unit-time jobs and we show that a more general problem, where the recalibration of the machine is not instantaneous but takes time, can be solved in polynomial time.

  • Open Access

    Maximum Rooted Connected Expansion

    by Ioannis Lamprou, Russell Martin, Sven Schewe, Ioannis Sigalas, Vassilis Zissimopoulos

    Prefetching constitutes a valuable tool toward efficient Web surfing. As a result, estimating the amount of resources that need to be preloaded during a surfer's browsing becomes an important task. In this regard, prefetching can be modeled as a two-player combinatorial game [Fomin et al., Theoretical Computer Science 2014], where a surfer and a marker alternately play on a given graph (representing the Web graph). During its turn, the marker chooses a set of $k$ nodes to mark (prefetch), whereas the surfer, represented as a token resting on graph nodes, moves to a neighboring node (Web resource). The surfer's objective is to reach an unmarked node before all nodes become marked and the marker wins. Intuitively, since the surfer is step-by-step traversing a subset of nodes in the Web graph, a satisfactory prefetching procedure would load in cache all resources lying in the neighborhood of this growing subset. Motivated by the above, we consider the following problem to which we refer to as the Maximum Rooted Connected Expansion (MRCE) problem. Given a graph $G$ and a root node $v_0$, we wish to find a subset of vertices $S$ such that $S$ is connected, $S$ contains $v_0$ and the ratio $|N[S]|/|S|$ is maximized, where $N[S]$ denotes the closed neighborhood of $S$, that is, $N[S]$ contains all nodes in $S$ and all nodes with at least one neighbor in $S$. We prove that the problem is NP-hard even when the input graph $G$ is restricted to be a split graph. On the positive side, we demonstrate a polynomial time approximation scheme for split graphs. Furthermore, we present a $\frac{1}{6}(1-\frac{1}{e})$-approximation algorithm for general graphs based on techniques for the Budgeted Connected Domination problem [Khuller et al., SODA 2014]. Finally, we provide a polynomial-time algorithm for the special case of interval graphs.

  • Open Access

    Optimal Data Placement on Networks With Constant Number of Clients

    by Eric Angel, Evripidis Bampis, Gerasimos G. Pollatos, Vassilis Zissimopoulos

    We introduce optimal algorithms for the problems of data placement (DP) and page placement (PP) in networks with a constant number of clients each of which has limited storage availability and issues requests for data objects. The objective for both problems is to efficiently utilize each client's storage (deciding where to place replicas of objects) so that the total incurred access and installation cost over all clients is minimized. In the PP problem an extra constraint on the maximum number of clients served by a single client must be satisfied. Our algorithms solve both problems optimally when all objects have uniform lengths. When objects lengths are non-uniform we also find the optimal solution, albeit a small, asymptotically tight violation of each client's storage size by $\epsilon$lmax where lmax is the maximum length of the objects and $\epsilon$ some arbitrarily small positive constant. We make no assumption on the underlying topology of the network (metric, ultrametric etc.), thus obtaining the first non-trivial results for non-metric data placement problems.

  • Dynamic bottleneck optimization for k-edge and 2-vertex connectivity

    by Orestis A. Telelis, Vassilis Zissimopoulos

    • 19 October 2007
    • Published by HAL in HAL
    Open Access

    A robust 2-stage version for the STEINER TREE problem

    by Vangelis Th Paschos, Orestis Teletis, Vassilis Zissimopoulos

    In this paper we consider a robust version for STEINER TREE. Under it, the problem is defined in a two-stage setting over a complete weighted graph whose vertices are associated with a probability of presence in the second stage. A first-stage feasible solution on the input graph might become infeasible in the second stage, when certain vertices of the graph fail (with the specified probability). Therefore, a well defined modification strategy is devised which transforms a partial solution to a feasible second-stage solution. The objective is to devise an algorithm for the first-stage solution (sometimes called the a priori or anticipatory solution) so that the expected second-stage solution cost is minimized. An important feature of this framework is that the modification strategy is essentially a part of the problem, while algorithmic treatment is required in the construction of the anticipatory solution. We provide complexity and approximation results regarding a modification strategy based upon the well known depth-first-search algorithm.