A class of convex programs with applications to computational geometry

1 January 1992

proceedings article
Published by Association for Computing Machinery (ACM)

p. 9-15
https://doi.org/10.1145/142675.142681

Abstract

We consider the solution of convex programs in a small number of variables but large number of constraints, where all but a small number of the constraints are linear. We develop a general framework for obtaining algorithms for these problems which run in time linear in the number of constraints. We give an application to computing minimum spanning ellipsoids in fixed dimension.

Keywords

LINEAR PROGRAMMING
COMPUTATIONAL GEOMETRY
CONVEX PROGRAMMING
COMBINATORIAL OPTIMIZATION

This publication has 0 references indexed in Scilit: