A. Lingas

activity

20092024

most citedExact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications

4 citations · 10 across the 24 of their papers we have counts for

collaborators

25 papers

cs.CG2024

The Voronoi Diagram of Weakly Smooth Planar Point Sets in $O (lo g n)$ Deterministic Rounds on the Congested Clique

Jesper Jansson, Christos Levcopoulos, Andrzej Lingas

We study the problem of computing the Voronoi diagram of a set of $n^{2}$ points with $O (lo g n)$ -bit coordinates in the Euclidean plane in a substantially sublinear in $n$ number of…

cs.DS2023

$(min, +)$ Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences

Andrzej Lingas, Mia Persson

We study the time complexity of computing the $(min, +)$ matrix product of two $n \times n$ integer matrices in terms of $n$ and the number of monotone subsequences the rows of the…

cs.DS2023

Finding Small Complete Subgraphs Efficiently

Ke Chen, Adrian Dumitrescu, Andrzej Lingas

(I) We revisit the algorithmic problem of finding all triangles in a graph $G = (V, E)$ with $n$ vertices and $m$ edges. According to a result of Chiba and Nishizeki (1985), this task…

cs.CC2023

Improved Lower Bounds for Monotone q-Multilinear Boolean Circuits

Andrzej Lingas, Mia Persson

A monotone Boolean circuit is composed of OR gates, AND gates and input gates corresponding to the input variables and the Boolean constants. It is $q$ -multilinear if for each its…

cs.DC2023

Convex Hulls, Triangulations, and Voronoi Diagrams of Planar Point Sets on the Congested Clique

Jesper Jansson, Christos Levcopoulos, Andrzej Lingas +1

We consider geometric problems on planar $n^{2}$ -point sets in the congested clique model. Initially, each node in the $n$ -clique network holds a batch of $n$ distinct points in the…

cs.DS2022

Perpetual maintenance of machines with different urgency requirements

Leszek Gąsieniec, Tomasz Jurdziński, Ralf Klasing +4

A garden $G$ is populated by $n \geq 1$ bamboos $b_{1}, b_{2}, ..., b_{n}$ with the respective daily growth rates $h_{1} \geq h_{2} \geq \dots \geq h_{n}$ . It is assumed that the initial heights of…

The Voronoi Diagram of Weakly Smooth Planar Point Sets in O(logn) Deterministic Rounds on the Congested Clique