4 citations · 6 across the 5 of their papers we have counts for
11 papers
On the Approximability of Multistage Min-Sum Set Cover
Dimitris Fotakis, Panagiotis Kostopanagiotis, Vasileios Nakos +2
We investigate the polynomial-time approximability of the multistage version of Min-Sum Set Cover (), a natural and intriguing generalization of the classical List U…
Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution
Karl Bringmann, Nick Fischer, Vasileios Nakos
Computing the convolution of two length- integer vectors is a core problem in several disciplines. It frequently comes up in algorithms for Knapsack, -SUM, A…
Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution
Karl Bringmann, Nick Fischer, Vasileios Nakos
Computing the convolution of two length- vectors is an ubiquitous computational primitive. Applications range from string problems to Knapsack-type problems, an…
Fast -fold Boolean Convolution via Additive Combinatorics
Karl Bringmann, Vasileios Nakos
We consider the problem of computing the Boolean convolution (with wraparound) of ~vectors of dimension , or, equivalently, the problem of computing the sumset $A_1+A_2+\ldot…
Fast and Simple Modular Subset Sum
Kyriakos Axiotis, Arturs Backurs, Karl Bringmann +4
We revisit the Subset Sum problem over the finite cyclic group for some given integer . A series of recent works has provided near-optimal algorithms for this pro…
Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time
Mahdi Cheraghchi, Vasileios Nakos
In the long-studied problem of combinatorial group testing, one is asked to detect a set of defective items out of a population of size , using disjunctive measure…