Zobrazeno 1 - 10
of 29
pro vyhledávání: '"Tsidulko, Oxana"'
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:
Networks 76(4):485-508, 2020
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 edges of $R$. We prove that RPP is WK[1]-complete parameterized by the number a
Externí odkaz:
http://arxiv.org/abs/1812.10131
Publikováno v:
Discrete Applied Mathematics, 298: 110-128, 2021
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 problems with multiple matroid constraints. We complement our tractabil
Externí odkaz:
http://arxiv.org/abs/1806.11527
Publikováno v:
Networks, 75(1):34-63, 2020
Given a graph $G=(V,E)$, two vertices $s,t\in V$, and two integers $k,\ell$, the Short Secluded Path problem is to find a simple $s$-$t$-path with at most $k$ vertices and $\ell$ neighbors. We study the parameterized complexity of the problem with re
Externí odkaz:
http://arxiv.org/abs/1806.09540
Publikováno v:
In Discrete Applied Mathematics 31 July 2021 298:110-128
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
In Operations Research Letters March 2021 49(2):270-277