Oxana Yu. Tsidulko
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Oxana Yu. Tsidulko has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Edward Kh. Gimadi
Sobolev Institute of Mathematics
12 shared publications - René van Bevern
Department of Mechanics and Mathematics, Novosibirsk State University, Novosibirsk, Russian Federation
10 shared publications - Till Fluschnik
Humboldt-Universität zu Berlin
5 shared publications Ivan Rykov
Sobolev Institute of Mathematics
2 shared publications- Philipp Zschoche
Algorithmics and Computational Complexity, Technische Universität Berlin, Berlin, Germany
2 shared publications - A. A. Skretneva
Sobolev Institute of Mathematics SB RAS, Novosibirsk State University, Russia
1 shared publication
Latest Publications
- Open Access
- 27 December 2025
- Published by Ural Federal University in Ural mathematical journal
- Vol. 11 (2) , 100-118
EDGE-DISJOINT SPANNING TREES OF ARBITRARY BOUNDED DIAMETER ON RANDOM INPUTS
We consider the following NP-hard generalization of the Minimum Spanning Tree problem. Given an undirected \(n\)-vertex edge-weighted complete graph and integers \(d\) and \(m\), find \(m\) edge-disjoint spanning trees of diameter at most \(d\) with minimum total weight. We propose a new polynomial-time approximation algorithm for the problem and study its performance guarantees on random inputs, that is, when the edge weights of the graph are i. i. d. random variables. We show that under mild conditions on the distribution parameters the proposed algorithm is asymptotically optimal for the case of continuous and discrete uniform distribution on \([a_n, b_n]\), \(a_n>0\), the shifted exponential distribution with shift \(a_n>0\), and distributions dominating the above. In contrast to a number of previous results for related problems, the new algorithm is asymptotically optimal not only if \(d\) tends to infinity with \(n\), but for constant \(d\) as well.- 27 December 2025
- Published by Ural Federal University in Ural mathematical journal
- Vol. 11 (2) , 100-118
Open AccessEDGE-DISJOINT SPANNING TREES OF ARBITRARY BOUNDED DIAMETER ON RANDOM INPUTS
We consider the following NP-hard generalization of the Minimum Spanning Tree problem. Given an undirected \(n\)-vertex edge-weighted complete graph and integers \(d\) and \(m\), find \(m\) edge-disjoint spanning trees of diameter at most \(d\) with minimum total weight. We propose a new polynomial-time approximation algorithm for the problem and study its performance guarantees on random inputs, that is, when the edge weights of the graph are i. i. d. random variables. We show that under mild conditions on the distribution parameters the proposed algorithm is asymptotically optimal for the case of continuous and discrete uniform distribution on \([a_n, b_n]\), \(a_n>0\), the shifted exponential distribution with shift \(a_n>0\), and distributions dominating the above. In contrast to a number of previous results for related problems, the new algorithm is asymptotically optimal not only if \(d\) tends to infinity with \(n\), but for constant \(d\) as well. - 15 April 2025
- Published by Springer Nature
- p. 249-261
An Asymptotically Optimal Algorithm for the Minimum Weight Spanning Tree with Arbitrarily Bounded Diameter on Random Inputs
- 15 April 2025
- Published by Springer Nature
- p. 249-261
An Asymptotically Optimal Algorithm for the Minimum Weight Spanning Tree with Arbitrarily Bounded Diameter on Random Inputs
- 13 September 2023
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 139
Serial and parallel kernelization of Multiple Hitting Set parameterized by the Dilworth number, implemented on the GPU
- 13 September 2023
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 139
Serial and parallel kernelization of Multiple Hitting Set parameterized by the Dilworth number, implemented on the GPU
- 26 July 2021
- Published by Pleiades Publishing Ltd in Proceedings of the Steklov Institute of Mathematics
- Vol. 313 (S1) , S58-S72
On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines
We study the network facility location problem with constraints on the capacities of communication lines, called Restricted Facility Location Problem (RFLP). It is required to locate facilities at the vertices of a given network graph so as to simultaneously satisfy at minimum cost the demands of customers located at the vertices of the graph. We consider two statements of the problem: the multiple allocation RFLP, where the demand of a customer can be satisfied jointly by several facilities, and the single allocation RFLP, where the demand of a customer must be entirely satisfied by a single facility. We show that the single allocation RFLP is NP-hard even if the network is a simple path and strongly NP-hard if the network is a tree. The multiple allocation RFLP is weakly NP-hard on trees. For this problem, we propose a pseudopolynomial-time algorithm for the case where the network graph has constant treewidth and a linear-time algorithm for the case where the network is a simple path.
- 26 July 2021
- Published by Pleiades Publishing Ltd in Proceedings of the Steklov Institute of Mathematics
- Vol. 313 (S1) , S58-S72
On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines
We study the network facility location problem with constraints on the capacities of communication lines, called Restricted Facility Location Problem (RFLP). It is required to locate facilities at the vertices of a given network graph so as to simultaneously satisfy at minimum cost the demands of customers located at the vertices of the graph. We consider two statements of the problem: the multiple allocation RFLP, where the demand of a customer can be satisfied jointly by several facilities, and the single allocation RFLP, where the demand of a customer must be entirely satisfied by a single facility. We show that the single allocation RFLP is NP-hard even if the network is a simple path and strongly NP-hard if the network is a tree. The multiple allocation RFLP is weakly NP-hard on trees. For this problem, we propose a pseudopolynomial-time algorithm for the case where the network graph has constant treewidth and a linear-time algorithm for the case where the network is a simple path.
- 1 July 2021
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 298, 110-128
Representative families for matroid intersections, with applications to location, packing, and covering problems
- 1 July 2021
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 298, 110-128
Representative families for matroid intersections, with applications to location, packing, and covering problems
- 1 March 2021
- Published by Elsevier in Operations Research Letters
- Vol. 49 (2) , 270-277
The Hierarchical Chinese Postman Problem: The slightest disorder makes it hard, yet disconnectedness is manageable
- 1 March 2021
- Published by Elsevier in Operations Research Letters
- Vol. 49 (2) , 270-277
The Hierarchical Chinese Postman Problem: The slightest disorder makes it hard, yet disconnectedness is manageable
- Open Access
Representative families for matroid intersections, with applications to location, packing, and covering problems
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 tractability results by hardness results.
Open AccessRepresentative families for matroid intersections, with applications to location, packing, and covering problems
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 tractability results by hardness results.
- Open Access
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 edges of $R$. We prove that RPP is WK[1]-complete parameterized by the number and cost $d$ of edges traversed additionally to the required ones. Thus, in particular, RPP instances cannot be polynomial-time compressed to instances of size polynomial in $d$ unless the polynomial-time hierarchy collapses. In contrast, denoting by $b\leq 2d$ the number of vertices incident to an odd number of edges of $R$ and by $c\leq d$ the number of connected components formed by the edges in $R$, we show how to reduce any RPP instance $I$ to an RPP instance $I'$ with $2b+O(c/\varepsilon)$ vertices in $O(n^3)$ time so that any $\alpha$-approximate solution for $I'$ gives an $\alpha(1+\varepsilon)$-approximate solution for $I$, for any $\alpha\geq 1$ and $\varepsilon>0$. That is, we provide a polynomial-size approximate kernelization scheme (PSAKS). We experimentally evaluate it on wide-spread benchmark data sets as well as on two real snow plowing instances from Berlin. On instances with few connected components, the number of vertices and required edges is reduced to about $50\,\%$ at a $1\,\%$ solution quality loss. We also make first steps towards a PSAKS for the parameter $c$.Open AccessOn 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 edges of $R$. We prove that RPP is WK[1]-complete parameterized by the number and cost $d$ of edges traversed additionally to the required ones. Thus, in particular, RPP instances cannot be polynomial-time compressed to instances of size polynomial in $d$ unless the polynomial-time hierarchy collapses. In contrast, denoting by $b\leq 2d$ the number of vertices incident to an odd number of edges of $R$ and by $c\leq d$ the number of connected components formed by the edges in $R$, we show how to reduce any RPP instance $I$ to an RPP instance $I'$ with $2b+O(c/\varepsilon)$ vertices in $O(n^3)$ time so that any $\alpha$-approximate solution for $I'$ gives an $\alpha(1+\varepsilon)$-approximate solution for $I$, for any $\alpha\geq 1$ and $\varepsilon>0$. That is, we provide a polynomial-size approximate kernelization scheme (PSAKS). We experimentally evaluate it on wide-spread benchmark data sets as well as on two real snow plowing instances from Berlin. On instances with few connected components, the number of vertices and required edges is reduced to about $50\,\%$ at a $1\,\%$ solution quality loss. We also make first steps towards a PSAKS for the parameter $c$. - 22 January 2020
- Published by Springer Nature
- p. 201-207
Asymptotically Optimal Algorithms for the Prize-Collecting Traveling Salesman Problem on Random Inputs
- 22 January 2020
- Published by Springer Nature
- p. 201-207
Asymptotically Optimal Algorithms for the Prize-Collecting Traveling Salesman Problem on Random Inputs