Zobrazeno 1 - 10
of 160
pro vyhledávání: '"Bevern, René"'
Autor:
van Bevern, René, Skachkov, Daniel A.
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 complete graph. We present a problem kernel with $\tau^2+\tau$ vertice
Externí odkaz:
http://arxiv.org/abs/2207.08678
Publikováno v:
Operations Research Letters 51:446-452, 2023
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 number of requests overlapping in time. We also present a simple polynom
Externí odkaz:
http://arxiv.org/abs/2205.08769
Autor:
van Bevern, René, Kirilin, Artem M., Skachkov, Daniel A., Smirnov, Pavel V., Tsidulko, Oxana Yu.
Publikováno v:
Journal of Computer and System Sciences 139:103479, 2024
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-known data reduction algorithm due to Weihe, we show a problem kernel
Externí odkaz:
http://arxiv.org/abs/2109.06042
Autor:
van Bevern, René, Kirilin, Artem M., Skachkov, Daniel A., Smirnov, Pavel V., Tsidulko, Oxana Yu.
Publikováno v:
In Journal of Computer and System Sciences February 2024 139
Publikováno v:
Operations Research Letters, 49(2): 270-277, 2021
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 show that the special case with connected classes is NP-hard even on o
Externí odkaz:
http://arxiv.org/abs/2011.04022
Publikováno v:
Historia Mathematica, 53:118-127, 2020
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 Christofides in 1976 and is well known as "the Christofides algorithm"
Externí odkaz:
http://arxiv.org/abs/2004.02437
Autor:
van Bevern, René, Smirnov, Pavel V.
Publikováno v:
Information Processing Letters 163:105998, 2020
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 structure, we show that problem kernels of asymptotical
Externí odkaz:
http://arxiv.org/abs/2003.04578
Publikováno v:
Discrete Applied Mathematics 328:117-133, 2023
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 reduced to an equivalent instance with size upper-bounded by a function of
Externí odkaz:
http://arxiv.org/abs/1910.00277
Publikováno v:
In Discrete Applied Mathematics 31 March 2023 328:117-133