Abstract
A new modification of the double description method is proposed for constructing the skeleton of a polyhedral cone. Theoretical results and a numerical experiment show that the modification is considerably superior to the original algorithm in terms of speed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
F. Preparata and M. Shamos, Computational Geometry: An Introduction (Springer-Verlag, New York, 1985; Mir, Moscow, 1989).
D. Avis, D. Bremner, and R. Seidel, “How Good Are Convex Hull Algorithms?” Comput. Geom. Theory Appl. 7(5, 6), 265–301 (1997).
T. S. Motzkin, H. Raiffa, G. L. Thompson, and R. M. Thrall, “The Double Description Method,” Contributions to the Theory of Games (Princeton University Press, Princeton, N. J., 1953; Fizmatgiz, Moscow, 1961).
E. Burger, “Uber homoge nelineare Ungleichungssysteme,” Angewandte Math. Mech. 36(3/4), 135–139 (1956).
N. V. Chernikova, “Algorithm for Finding a General Formula for the Nonnegative Solutions of a System of Linear Equations,” USSR Math. Math. Phys. 4(4), 151–158 (1964).
N. V. Chernikova, “Algorithm for Finding a General Formula for the Nonnegative Solutions of a System of Linear Inequalities,” USSR Math. Math. Phys. 5(2), 228–233 (1965).
S. N. Chernikov, Linear Inequalities (Nauka, Moscow, 1968) [in Russian].
S. I. Veselov, I. E. Parubochii, and V. N. Shevchenko, “A Software Program for Finding the Skeleton of the Cone of Nonnegative Solutions of a System of Linear Inequalities,” in System and Applied Software Programs (Gor’kov. Gos. Univ., Gor’kii, 1984), pp. 83–92 [in Russian].
F. Fernandez and P. Quinton, “Extension of Chernikova’s Algorithm for Solving General Mixed Linear Programming Problems,” Res. Rep. RR-0943 (INRIA, Rennes, 1988).
H. Le Verge, “A Note on Chernikova’s Algorithm,” Res. Rep. RR-1662 (INRIA, Rennes, 1992).
K. Fukuda and A. Prodon, “Double Description Method Revisited,” Combinatorics and Computer Science (Springer-Verlag, New York, 1996), pp. 91–111.
V. N. Shevchenko and A. Yu. Chirkov, “On the Complexity of Finding the Skeleton of a Cone,” Proceedings of 10th All-Russia Conference on Mathematical Programming and Applications (Ural. Otd. Ross. Akad. Nauk, Yekaterinburg, 1997), p. 237.
V. N. Shevchenko and D. V. Gruzdev, “A Modification of the Fourier-Motzkin Algorithm for Constructing Triangulations,” Diskret. Anal. Issled. Oper., Ser. 2. 10(10), 53–64 (2003).
O. L. Chernykh, “Construction of the Convex Hull of a Finite Set of Points Using Triangulation,” USSR Comput. Math. Math. Phys. 31(8), 80–86 (1991).
B. Chaselle, “An Optimal Convex Hull Algorithm in Any Fixed Dimension,” Discrete Comput. Geom., No. 10, 377–409 (1993).
A. Schrijver, Theory of Linear and Integer Programming (Wiley, Chichester, 1986; Mir, Moscow, 1991).
M. M. Deza and M. Laurent, Geometry of Cuts and Metrics (Springer-Verlag, Berlin, 1997; MTsNMO, Moscow, 2001) [in Russian].
N. Yu. Zolotykh and S. S. Lyalin, “A Parallel Algorithm for Finding the General Solution of the System of Linear Inequalities,” Vestn. Nizhegorod. Gos. Univ., No. 5, 193–199 (2009).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © N.Yu. Zolotykh, 2012, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2012, Vol. 52, No. 1, pp. 153–163.
Rights and permissions
About this article
Cite this article
Zolotykh, N.Y. New modification of the double description method for constructing the skeleton of a polyhedral cone. Comput. Math. and Math. Phys. 52, 146–156 (2012). https://doi.org/10.1134/S0965542512010162
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0965542512010162