On the dynamic problem of computing generators of a polyhedral cone

S. I. Bastrakov ; N. Yu. Zolotykh

Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika, Tome 9 (2017) no. 1, pp. 5-12

Résumé

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.

Détail

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