Zobrazeno 1 - 10
of 26
pro vyhledávání: '"Edward Kh. Gimadi"'
Autor:
Edward Kh. Gimadi, Ivan A. Rykov
Publikováno v:
Communications in Computer and Information Science ISBN: 9783030712136
AIST (Supplement)
AIST (Supplement)
We consider the problem of finding m edge-disjoint k-cycles covers formulated in d-dimensional Euclidean space. We construct a polynomial-time approximation algorithm for this problem and derive conditions of its asymptotical optimality.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2301ee8c151b15a9d6d1af0d46da8613
https://doi.org/10.1007/978-3-030-71214-3_21
https://doi.org/10.1007/978-3-030-71214-3_21
Publikováno v:
Communications in Computer and Information Science ISBN: 9783030712136
AIST (Supplement)
AIST (Supplement)
In this article we consider a three-level facility location problem on a tree-like network under the restriction that the transportation costs for a unit of production from one node to another is equal to the sum of the edges in the path connecting t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::43b866584f13a4ca94b4d803946fee4e
https://doi.org/10.1007/978-3-030-71214-3_22
https://doi.org/10.1007/978-3-030-71214-3_22
Publikováno v:
Mathematical Optimization Theory and Operations Research ISBN: 9783030778750
MOTOR
MOTOR
We consider the intractable problem of finding several edge-disjoint spanning trees of a given diameter in an graph with random edge weights. Earlier, we have implemented an asymptotically optimal approach for this problem in the case of directed gra
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::93917238e64557a6bc8b67cb07def081
https://doi.org/10.1007/978-3-030-77876-7_5
https://doi.org/10.1007/978-3-030-77876-7_5
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
Autor:
Edward Kh. Gimadi, Ivan A. Rykov
Publikováno v:
Mathematical Optimization Theory and Operations Research ISBN: 9783030499877
MOTOR
MOTOR
We consider the intractable problem of finding m edge-disjoint vertex covers in d-dimensional normed space with maximum total weight, such that each of them has exactly k cycles. We construct a polynomial-time approximation algorithm for solving this
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4f66c71968bc5f7ebcffe558b4f7ffe0
https://doi.org/10.1007/978-3-030-49988-4_6
https://doi.org/10.1007/978-3-030-49988-4_6
Publikováno v:
Optimization and Applications ISBN: 9783030628666
OPTIMA
OPTIMA
We give a new approximation polynomial time algorithm for one of the intractable problem of finding given-diameter Minimum Spanning Tree (MST) on n-vertex complete graph with randomly weighted edges. A significant advantage of this algorithm is that
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b62af0fae4cfee1134efd26b28578f89
https://doi.org/10.1007/978-3-030-62867-3_9
https://doi.org/10.1007/978-3-030-62867-3_9
Autor:
Anna A. Kurochkina, Edward Kh. Gimadi
Publikováno v:
Communications in Computer and Information Science ISBN: 9783030109332
We show that the facility location problem with uniform hard capacities can be solved by the Ageev’s algorithm in \(O(m^3n^2)\) time, where m is the number of facilities and n is the number of clients. This improves the results \(O(m^5 n^2)\) of Ag
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::dada26bfc56e7ead9b126c58357fbb6c
https://doi.org/10.1007/978-3-030-10934-9_9
https://doi.org/10.1007/978-3-030-10934-9_9
Autor:
Edward Kh. Gimadi, Ekaterina Yu. Shin
Publikováno v:
Mathematical Optimization Theory and Operations Research ISBN: 9783030333935
MOTOR (2)
MOTOR (2)
We give an approximation deterministic algorithm for solving the Random MST with given diameter of directed graph. The problem is NP-hard. Algorithm has a quadratic time complexity. A probabilistic analysis was performed under conditions that edge we
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::09a78097d5ccaffe2cc9388aaa1f6ca8
https://doi.org/10.1007/978-3-030-33394-2_3
https://doi.org/10.1007/978-3-030-33394-2_3
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
Publikováno v:
Communications in Computer and Information Science ISBN: 9783319937991
We consider a problem of finding a subset of the smallest size in the given set of vectors such that the norm of sum vector is greater or equal to some given value. We show that the problem can be solved optimally with the same complexity as the prob
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f77c01ad83bb29b8b3c2a0ddde823e2e
https://doi.org/10.1007/978-3-319-93800-4_11
https://doi.org/10.1007/978-3-319-93800-4_11