Vestnik Yuzhno-Ural'skogo Gosudarstvennogo Universiteta. Seriya "Matematika. Mekhanika. Fizika"
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Vestn. Yuzhno-Ural. Gos. Un-ta. Ser. Matem. Mekh. Fiz.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Vestn. Yuzhno-Ural. Gos. Un-ta. Ser. Matem. Mekh. Fiz., 2017, Volume 9, Issue 1, Pages 5–12 (Mi vyurm322)  

Mathematics

On the dynamic problem of computing generators of a polyhedral cone

S. I. Bastrakov, N. Yu. Zolotykh

Lobachevsky State University of Nizhni Novgorod, Nizhniy Novgorod, Russian Federation

Abstract: This paper considers a dynamic problem of computing generators of a polyhedral cone. The problem is to sequentially perform operations of adding and removing inequalities from a facet description of the polyhedral cone with a corresponding re-computation of generators. The application of a double description method for both operations is discussed and complexity estimation is given in the paper.
Adding a new inequality corresponds to a single step of the double description method. It can be performed with time complexity being quadratic or cubic of the input size for the current step, depending on the modification of the method and adjacency tests chosen. We give complexity bounds for adding a single inequality with widely used algebraic and combinatorial adjacency tests.
The problem of removing inequalities is intrinsically much harder, compared to adding inequalities. We briefly describe the naive and incremental algorithms and show an example with output size being superpolynomial of the input size in case of removing a single inequality. A subclass of problems with certain adjacency properties is investigated, for this subclass we prove that the output size is bounded by a quadratic function of the input size. Finally, we prove that for the distinguished subclass any finite sequence of adding and removing inequalities can be performed in polynomial time of the input size.

Keywords: system of linear inequalities, polyhedral cone, computing dual description, double description method.

DOI: https://doi.org/10.14529/mmph170101

Full text: PDF file (221 kB)
References: PDF file   HTML file

UDC: 519.6
Received: 11.10.2016

Citation: S. I. Bastrakov, N. Yu. Zolotykh, “On the dynamic problem of computing generators of a polyhedral cone”, Vestn. Yuzhno-Ural. Gos. Un-ta. Ser. Matem. Mekh. Fiz., 9:1 (2017), 5–12

Citation in format AMSBIB
\Bibitem{BasZol17}
\by S.~I.~Bastrakov, N.~Yu.~Zolotykh
\paper On the dynamic problem of computing generators of a polyhedral cone
\jour Vestn. Yuzhno-Ural. Gos. Un-ta. Ser. Matem. Mekh. Fiz.
\yr 2017
\vol 9
\issue 1
\pages 5--12
\mathnet{http://mi.mathnet.ru/vyurm322}
\crossref{https://doi.org/10.14529/mmph170101}
\elib{https://elibrary.ru/item.asp?id=28113988}


Linking options:
  • http://mi.mathnet.ru/eng/vyurm322
  • http://mi.mathnet.ru/eng/vyurm/v9/i1/p5

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Number of views:
    This page:135
    Full text:53
    References:22

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022