Zobrazeno 1 - 10
of 11
pro vyhledávání: '"Oxana Yu. Tsidulko"'
Publikováno v:
Discrete Applied Mathematics. 298:110-128
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
Publikováno v:
Networks. 76:485-508
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
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:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6c0cf6507a815ea4c63192a70217354c
http://arxiv.org/abs/2011.04022
http://arxiv.org/abs/2011.04022
Publikováno v:
Communications in Computer and Information Science ISBN: 9783030386023
We consider the Connected k-factor problem (k-CFP): given a complete edge-weighted n-vertex graph, the goal is to find a connected k-regular spanning subgraph of maximum or minimum total weight. The problem is called geometric, if the vertices of a g
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::86c3ccc2df106d8cbdc47a272093b018
https://doi.org/10.1007/978-3-030-38603-0_15
https://doi.org/10.1007/978-3-030-38603-0_15
Publikováno v:
Mathematical Optimization Theory and Operations Research ISBN: 9783030226282
MOTOR
MOTOR
Given a graph \(G=(V,E)\) with edge weights and a subset \(R\subseteq E\) of required edges, the NP-hard Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges of R. The number b of vertices incident to an o
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::87d8fdec301be70e2b0340dc7ed005ef
https://doi.org/10.1007/978-3-030-22629-9_20
https://doi.org/10.1007/978-3-030-22629-9_20
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783030174019
CIAC
CIAC
We consider an uncapacitated discrete facility location problem where the task is to decide which facilities to open and which clients to serve for maximum profit so that the facilities form an independent set in given facility-side matroids and the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3b83ea4e30cdedd200cc09b7094ab007
https://doi.org/10.1007/978-3-030-17402-6_6
https://doi.org/10.1007/978-3-030-17402-6_6
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:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b7779721ad8ff9173ef84d119115a3c4
http://arxiv.org/abs/1806.09540
http://arxiv.org/abs/1806.09540
Autor:
Oxana Yu. Tsidulko, Edward Kh. Gimadi
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783030110260
AIST
AIST
The known asymptotically optimal algorithm for the Euclidean maximum Traveling Salesman Problem by Serdukov builds approximate solution for the problem around the maximum-weight perfect matching. In this paper we are going to discuss an asymptoticall
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7b9b38faa23b1d9dd341bff09316ec9c
https://doi.org/10.1007/978-3-030-11027-7_27
https://doi.org/10.1007/978-3-030-11027-7_27
Autor:
Edward Kh. Gimadi, Oxana Yu. Tsidulko
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783319730127
AIST
AIST
We consider the maximum m-Peripatetic Salesman Problem (MAX m-PSP), which is a natural generalization of the classic Traveling Salesman Problem. The problem is strongly NP-hard. In this paper we propose two polynomial approximation algorithms for the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2cec6a02e80d0a25b7ba7e053dfa6e13
https://doi.org/10.1007/978-3-319-73013-4_28
https://doi.org/10.1007/978-3-319-73013-4_28
Publikováno v:
Discrete Optimization and Operations Research ISBN: 9783319449135
DOOR
DOOR
We study the m-Peripatetic Salesman Problem on random inputs. In earlier papers we proposed a polynomial asymptotically optimal algorithm for the m-PSP with different weight functions on random inputs. The probabilistic analysis carried out for that
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::782f48180c76338d5fd92fabab4b6fd9
https://doi.org/10.1007/978-3-319-44914-2_11
https://doi.org/10.1007/978-3-319-44914-2_11