66 citations · 457 across the 33 of their papers we have counts for
15 papers · 1 filter
A quadratic-order problem kernel for the traveling salesman problem parameterized by the vertex cover number
René van Bevern, Daniel A. Skachkov
The NP-hard graphical traveling salesman problem (GTSP) is to find a closed walk of total minimum weight that visits each vertex in an undirected edge-weighted and not necessarily…
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…
The Hierarchical Chinese Postman Problem: the slightest disorder makes it hard, yet disconnectedness is manageable
Vsevolod A. Afanasev, René van Bevern, Oxana Yu. Tsidulko
The Hierarchical Chinese Postman Problem is finding a shortest traversal of all edges of a graph respecting precedence constraints given by a partial order on classes of edges. We…
A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
René van Bevern, Viktoriia A. Slugina
One of the most fundamental results in combinatorial optimization is the polynomial-time 3/2-approximation algorithm for the metric traveling salesman problem. It was presented by…
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…
Polynomial-Time Data Reduction for Weighted Problems Beyond Additive Goal Functions
Matthias Bentert, René van Bevern, Till Fluschnik +2
Dealing with NP-hard problems, kernelization is a fundamental notion for polynomial-time data reduction with performance guarantees: in polynomial time, a problem instance is reduc…
On approximate data reduction for the Rural Postman Problem: Theory and experiments
René van Bevern, Till Fluschnik, Oxana Yu. Tsidulko
Given an undirected graph with edge weights and a subset of its edges, the Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges of…
Representative families for matroid intersections, with applications to location, packing, and covering problems
René van Bevern, Oxana Yu. Tsidulko, Philipp Zschoche
We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location p…
Parameterized algorithms and data reduction for the short secluded --path problem
René van Bevern, Till Fluschnik, Oxana Yu. Tsidulko
Given a graph , two vertices , and two integers , the Short Secluded Path problem is to find a simple --path with at most vertices and n…
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…
Fixed-Parameter Algorithms for DAG Partitioning
René van Bevern, Robert Bredereck, Morgan Chopin +4
Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. [ACM SIGKDD 2009] as DAG Partitioning: given an arc-weighted directed acyclic…
A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
René van Bevern, Rolf Niedermeier, Ondřej Suchý
We study the problem of non-preemptively scheduling jobs, each job with a release time , a deadline , and a processing time , on parallel identical machi…
A parameterized approximation algorithm for the mixed and windy Capacitated Arc Routing Problem: theory and experiments
René van Bevern, Christian Komusiewicz, Manuel Sorge
We prove that any polynomial-time -approximation algorithm for the -vertex metric asymmetric Traveling Salesperson Problem yields a polynomial-time -approximation…
Constant-factor approximations for Capacitated Arc Routing without triangle inequality
René van Bevern, Sepp Hartung, André Nichterlein +1
Given an undirected graph with edge costs and edge demands, the Capacitated Arc Routing problem (CARP) asks for minimum-cost routes for equal-capacity vehicles so as to satisfy all…