TY - JOUR
T1 - On the complexity of some basic problems in computational convexity
T2 - I. Containment problems
AU - Gritzmann, Peter
AU - Klee, Victor
PY - 1994/12/31
Y1 - 1994/12/31
N2 - This is the first part of a broader survey of computational convexity, an area of mathematics that has crystallized around a variety of results, problems and applications involving interactions among convex geometry, mathematical programming, and computer science. The paper begins with some general remarks on computational convexity and then summarizes three paradigmatic areas of the subject. However, the main focus of this part of the survey is on recent results that are related to the basic problems of computing, approximating, or measuring the convex sets which, among those in a given class, are the smallest that contain a given convex body K or are the largest contained in K. Particular subjects dealt with include optimal containment under homothety, under similarity and under affinity, and inner and outer radii. The final section outlines some applications of containment problems to questions in global optimization, pseudoboolean programming, sensitivity analysis of linear programming, orthogonal minimax regression, set separation, the existence problem for Hadamard matrices, weighing designs, and the growth rate of the pivot entries in Gaussian elimination.
AB - This is the first part of a broader survey of computational convexity, an area of mathematics that has crystallized around a variety of results, problems and applications involving interactions among convex geometry, mathematical programming, and computer science. The paper begins with some general remarks on computational convexity and then summarizes three paradigmatic areas of the subject. However, the main focus of this part of the survey is on recent results that are related to the basic problems of computing, approximating, or measuring the convex sets which, among those in a given class, are the smallest that contain a given convex body K or are the largest contained in K. Particular subjects dealt with include optimal containment under homothety, under similarity and under affinity, and inner and outer radii. The final section outlines some applications of containment problems to questions in global optimization, pseudoboolean programming, sensitivity analysis of linear programming, orthogonal minimax regression, set separation, the existence problem for Hadamard matrices, weighing designs, and the growth rate of the pivot entries in Gaussian elimination.
UR - http://www.scopus.com/inward/record.url?scp=0001535602&partnerID=8YFLogxK
U2 - 10.1016/0012-365X(94)00111-U
DO - 10.1016/0012-365X(94)00111-U
M3 - Article
AN - SCOPUS:0001535602
SN - 0012-365X
VL - 136
SP - 129
EP - 174
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 1-3
ER -