BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Vassilis Zissimopoulos

Vassilis Zissimopoulos appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsMachine Learning

Catalog footprint

What is connected

4works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

4 published item(s)

preprint2020arXiv

Calibrations Scheduling Problem with Arbitrary Lengths and Activation Length

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Too Much Information Kills Information: A Clustering Perspective

Clustering is one of the most fundamental tools in the artificial intelligence area, particularly in the pattern recognition and learning theory. In this paper, we propose a simple, but novel approach for variance-based k-clustering tasks, included in which is the widely known k-means clustering. The proposed approach picks a sampling subset from the given dataset and makes decisions based on the data information in the subset only. With certain assumptions, the resulting clustering is provably good to estimate the optimum of the variance-based objective with high probability. Extensive experiments on synthetic datasets and real-world datasets show that to obtain competitive results compared with k-means method (Llyod 1982) and k-means++ method (Arthur and Vassilvitskii 2007), we only need 7% information of the dataset. If we have up to 15% information of the dataset, then our algorithm outperforms both the k-means method and k-means++ method in at least 80% of the clustering tasks, in terms of the quality of clustering. Also, an extended algorithm based on the same idea guarantees a balanced k-clustering result.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Optimal Data Placement on Networks With Constant Number of Clients

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 $ε$lmax where lmax is the maximum length of the objects and $ε$ 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.

0 citations0 reviewsNo code linkedOpen access