Source author record

Antonis Skarlatos

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

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Machine Learning

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2024arXiv

Dynamic algorithms for k-center on graphs

In this paper we give the first efficient algorithms for the $k$ -center problem on dynamic graphs undergoing edge updates. In this problem, the goal is to partition the input into $k$ sets by choosing $k$ centers such that the maximum distance from any data point to its closest center is minimized. It is known that it is NP-hard to get a better than $2$ approximation for this problem. While in many applications the input may naturally be modeled as a graph, all prior works on $k$ -center problem in dynamic settings are on point sets in arbitrary metric spaces. In this paper, we give a deterministic decremental $(2+ε)$ -approximation algorithm and a randomized incremental $(4+ε)$ -approximation algorithm, both with amortized update time $kn^{o(1)}$ for weighted graphs. Moreover, we show a reduction that leads to a fully dynamic $(2+ε)$ -approximation algorithm for the $k$ -center problem, with worst-case update time that is within a factor $k$ of the state-of-the-art fully dynamic $(1+ε)$ -approximation single-source shortest paths algorithm in graphs. Matching this bound is a natural goalpost because the approximate distances of each vertex to its center can be used to maintain a $(2+ε)$ -approximation of the graph diameter and the fastest known algorithms for such a diameter approximation also rely on maintaining approximate single-source distances.

preprint2022arXiv

Computing Smallest Convex Intersecting Polygons

A polygon C is an intersecting polygon for a set O of objects in the plane if C intersects each object in O, where the polygon includes its interior. We study the problem of computing the minimum-perimeter intersecting polygon and the minimum-area convex intersecting polygon for a given set O of objects. We present an FPTAS for both problems for the case where O is a set of possibly intersecting convex polygons in the plane of total complexity n. Furthermore, we present an exact polynomial-time algorithm for the minimum-perimeter intersecting polygon for the case where O is a set of n possibly intersecting segments in the plane. So far, polynomial-time exact algorithms were only known for the minimum perimeter intersecting polygon of lines or of disjoint segments.

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.