6 papers · 1 filter
Fast approximate -center clustering in high dimensional spaces
Mirosław Kowaluk, Andrzej Lingas, Mia Persson
We study the design of efficient approximation algorithms for the -center clustering and minimum-diameter -clustering problems in high dimensional Euclidean and Hamming…
Approximate all-pairs Hamming distances and 0-1 matrix multiplication
Miroslaw Kowaluk, Andrzej Lingas, Mia Persson
Arslan showed that computing all-pairs Hamming distances is easily reducible to arithmetic 0-1 matrix multiplication (IPL 2018). We provide a reverse, linear-time reduction of arit…
Multiplication of 0-1 matrices via clustering
Jesper Jansson, Miroslaw Kowaluk, Andrzej Lingas +1
We study applications of clustering (in particular, the -center clustering problem) in the design of efficient and practical algorithms for computing an approximate and the exac…
Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences
Andrzej Lingas, Mia Persson
We study the time complexity of computing the matrix product of two integer matrices in terms of and the number of monotone subsequences the rows of the…
An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs
Andrzej Lingas, Mia Persson, Dzmitry Sledneu
A straightforward dynamic programming method for the single-source shortest paths problem (SSSP) in an edge-weighted directed acyclic graph (DAG) processes the vertices in a topolo…
Computing the Boolean product of two n\times n Boolean matrices using O(n^2) mechanical operation
Andrzej Lingas, Mia Persson
We study the problem of determining the Boolean product of two n\times n Boolean matrices in an unconventional computational model allowing for mechanical operations. We show that…