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

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

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.

Original languageEnglish
Title of host publicationMathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings
EditorsAlexander Kononov, Michael Khachay, Valery A. Kalyagin, Panos Pardalos
PublisherSpringer Gabler
Pages85-97
Number of pages13
ISBN (Print)9783030499877
DOIs
Publication statusPublished - 1 Jan 2020
Event19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020 - Novosibirsk, Russian Federation
Duration: 6 Jul 202010 Jul 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12095 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020
CountryRussian Federation
CityNovosibirsk
Period06.07.202010.07.2020

Keywords

  • Asymptotically optimal
  • Cycles cover
  • m-PSP
  • Normed space
  • Polynomial-time algorithm

Fingerprint Dive into the research topics of 'On Asymptotically Optimal Solvability of Max m-k-Cycles Cover Problem in a Normed Space'. Together they form a unique fingerprint.

Cite this