A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
R van Bevern, VA Slugina - Historia Mathematica, 2020 - Elsevier
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 …
approximation algorithm for the metric traveling salesman problem. It was presented by …
A -Approximation for Multiple TSP with a Variable Number of Depots
M Deppert, M Kaul, M Mnich - arXiv preprint arXiv:2307.07180, 2023 - arxiv.org
One of the most studied extensions of the famous Traveling Salesperson Problem (TSP) is
the {\sc Multiple TSP}: a set of $ m\geq 1$ salespersons collectively traverses a set of $ n …
the {\sc Multiple TSP}: a set of $ m\geq 1$ salespersons collectively traverses a set of $ n …
Optimal-size problem kernels for d-hitting set in linear time and space
R van Bevern, PV Smirnov - Information Processing Letters, 2020 - Elsevier
The known linear-time kernelizations for d-Hitting Set guarantee linear worst-case running
times using a quadratic-size data structure (that is not fully initialized). Getting rid of this data …
times using a quadratic-size data structure (that is not fully initialized). Getting rid of this data …
Kernelization of counting problems
We introduce a new framework for the analysis of preprocessing routines for parameterized
counting problems. Existing frameworks that encapsulate parameterized counting problems …
counting problems. Existing frameworks that encapsulate parameterized counting problems …
On approximate data reduction for the Rural Postman Problem: Theory and experiments
Given an undirected graph with edge weights and a subset R of its edges, the Rural
Postman Problem (RPP) is to find a closed walk of minimum total weight containing all …
Postman Problem (RPP) is to find a closed walk of minimum total weight containing all …
The Hierarchical Chinese Postman Problem: The slightest disorder makes it hard, yet disconnectedness is manageable
Abstract 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 of a graph respecting precedence constraints given by a partial order on classes of …
Scheduling kernels via configuration LP
D Knop, M Koutecký - arXiv preprint arXiv:2003.02187, 2020 - arxiv.org
Makespan minimization (on parallel identical or unrelated machines) is arguably the most
natural and studied scheduling problem. A common approach in practical algorithm design …
natural and studied scheduling problem. A common approach in practical algorithm design …
On data reduction for dynamic vector bin packing
R van Bevern, A Melnikov, PV Smirnov… - Operations Research …, 2023 - Elsevier
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 …
arbitrary DVBP instances to size polynomial in the number of request types or in the maximal …
Parameterized algorithms for power-efficiently connecting wireless sensor networks: Theory and experiments
We study a problem of energy-efficiently connecting a symmetric wireless communication
network: given an n-vertex graph with edge weights, find a connected spanning subgraph of …
network: given an n-vertex graph with edge weights, find a connected spanning subgraph of …
Polynomial-time data reduction for weighted problems beyond additive goal functions
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 …
data reduction with performance guarantees: in polynomial time, a problem instance is …