10 citations · 16 across the 4 of their papers we have counts for
4 papers · 1 filter
On data reduction for dynamic vector bin packing
René van Bevern, Andrey Melnikov, Pavel Smirnov +1
We study a dynamic vector bin packing (DVBP) problem. We show hardness for shrinking arbitrary DVBP instances to size polynomial in the number of request types or in the maximal nu…
Serial and parallel kernelization of Multiple Hitting Set parameterized by the Dilworth number, implemented on the GPU
René van Bevern, Artem M. Kirilin, Daniel A. Skachkov +2
The NP-hard Multiple Hitting Set problem is finding a minimum-cardinality set intersecting each of the sets in a given input collection a given number of times. Generalizing a well…
Optimal-size problem kernels for -Hitting Set in linear time and space
René van Bevern, Pavel V. Smirnov
The known linear-time kernelizations for -Hitting Set guarantee linear worst-case running times using a quadratic-size data structure (that is not fully initialized). Getting ri…
Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
Matthias Bentert, René van Bevern, André Nichterlein +2
We study an NP-hard problem motivated by energy-efficiently maintaining the connectivity of a symmetric wireless communication network: Given an edge-weighted -vertex graph, fin…