On Asymptotically Optimal Solvability of Max m-k-Cycles Cover Problem in a Normed Space

Edward Kh Gimadi; Ivan A. Rykov

doi:10.1007/978-3-030-49988-4_6

On Asymptotically Optimal Solvability of Max m-k-Cycles Cover Problem in a Normed Space

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › рецензирование

Аннотация

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 problem and derive conditions of its asymptotical optimality.

Язык оригинала	английский
Название основной публикации	Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings
Редакторы	Alexander Kononov, Michael Khachay, Valery A. Kalyagin, Panos Pardalos
Издатель	Springer Gabler
Страницы	85-97
Число страниц	13
ISBN (печатное издание)	9783030499877
DOI	https://doi.org/10.1007/978-3-030-49988-4_6
Состояние	Опубликовано - 1 янв 2020
Событие	19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020 - Novosibirsk, Российская Федерация Продолжительность: 6 июл 2020 → 10 июл 2020

Серия публикаций

Название	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том	12095 LNCS
ISSN (печатное издание)	0302-9743
ISSN (электронное издание)	1611-3349

Конференция

Конференция	19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020
Страна	Российская Федерация
Город	Novosibirsk
Период	06.07.2020 → 10.07.2020

Доступ к документу

10.1007/978-3-030-49988-4_6

Link to publication in Scopus

Fingerprint Подробные сведения о темах исследования «On Asymptotically Optimal Solvability of Max m-k-Cycles Cover Problem in a Normed Space». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

Gimadi, E. K., & Rykov, I. A. (2020). On Asymptotically Optimal Solvability of Max m-k-Cycles Cover Problem in a Normed Space. В A. Kononov, M. Khachay, V. A. Kalyagin, & P. Pardalos (Ред.), Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings (стр. 85-97). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 12095 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-49988-4_6

Gimadi, Edward Kh ; Rykov, Ivan A. / On Asymptotically Optimal Solvability of Max m-k-Cycles Cover Problem in a Normed Space. Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings. редактор / Alexander Kononov ; Michael Khachay ; Valery A. Kalyagin ; Panos Pardalos. Springer Gabler, 2020. стр. 85-97 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f482b2b426e74f31bcfda49f1878c2d5,

title = "On Asymptotically Optimal Solvability of Max m-k-Cycles Cover Problem in a Normed Space",

abstract = "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 problem and derive conditions of its asymptotical optimality.",

keywords = "Asymptotically optimal, Cycles cover, m-PSP, Normed space, Polynomial-time algorithm",

author = "Gimadi, {Edward Kh} and Rykov, {Ivan A.}",

year = "2020",

month = jan,

day = "1",

doi = "10.1007/978-3-030-49988-4_6",

language = "English",

isbn = "9783030499877",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Gabler",

pages = "85--97",

editor = "Alexander Kononov and Michael Khachay and Kalyagin, {Valery A.} and Panos Pardalos",

booktitle = "Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings",

address = "Germany",

note = "19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020 ; Conference date: 06-07-2020 Through 10-07-2020",

}

Gimadi, EK & Rykov, IA 2020, On Asymptotically Optimal Solvability of Max m-k-Cycles Cover Problem in a Normed Space. в A Kononov, M Khachay, VA Kalyagin & P Pardalos (ред.), Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), том. 12095 LNCS, Springer Gabler, стр. 85-97, 19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020, Novosibirsk, Российская Федерация, 06.07.2020. https://doi.org/10.1007/978-3-030-49988-4_6

On Asymptotically Optimal Solvability of Max m-k-Cycles Cover Problem in a Normed Space. / Gimadi, Edward Kh ; Rykov, Ivan A.

Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings. ред. / Alexander Kononov; Michael Khachay; Valery A. Kalyagin; Panos Pardalos. Springer Gabler, 2020. стр. 85-97 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 12095 LNCS).

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › рецензирование

TY - GEN

T1 - On Asymptotically Optimal Solvability of Max m-k-Cycles Cover Problem in a Normed Space

AU - Gimadi, Edward Kh

AU - Rykov, Ivan A.

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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 problem and derive conditions of its asymptotical optimality.

AB - 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 problem and derive conditions of its asymptotical optimality.

KW - Asymptotically optimal

KW - Cycles cover

KW - m-PSP

KW - Normed space

KW - Polynomial-time algorithm

UR - http://www.scopus.com/inward/record.url?scp=85087756469&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-49988-4_6

DO - 10.1007/978-3-030-49988-4_6

M3 - Conference contribution

AN - SCOPUS:85087756469

SN - 9783030499877

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 85

EP - 97

BT - Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings

A2 - Kononov, Alexander

A2 - Khachay, Michael

A2 - Kalyagin, Valery A.

A2 - Pardalos, Panos

PB - Springer Gabler

T2 - 19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020

Y2 - 6 July 2020 through 10 July 2020

ER -

Gimadi EK , Rykov IA. On Asymptotically Optimal Solvability of Max m-k-Cycles Cover Problem in a Normed Space. В Kononov A, Khachay M, Kalyagin VA, Pardalos P, редакторы, Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings. Springer Gabler. 2020. стр. 85-97. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-49988-4_6