The Shapes of Polyhedra

Herbert Scarf, R. Kannan and Laszlo Lovasz
Additional contact information
R. Kannan: Carnegie-Mellon University
Laszlo Lovasz: Budapest & Princeton University

No 883, Cowles Foundation Discussion Papers from Cowles Foundation for Research in Economics, Yale University

Abstract: Let A be a real matrix of size (n+d+1)xn. We assume that all n x n submatrices of A are non-singular and define the condition number C = C(A) to be the ratio of the largest n x n subdeterminant of A to the smallest in absolute value. In addition we assume that there is a positive vector pi such that (pi)A = 0. This implies that for any b, the body K(b) = 'X such that AX 0, there exists a subset of the bodies K(b), of cardinality not larger than f(A) 1/2(log to the base 2 of (nC)/epsilon^{d}, such that every body is within epsilon of some member of the subset.

Keywords: Polyhedra; Banach-Mazur distance; Hubert metric; Lenstra's algorithm; integer programming; minimum (search for similar items in EconPapers)
Pages: 31 pages
Date: 1988-09
Note: CFP 753.
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Published in Mathematics of Operations Research (May 1990), 15(2): 364-390

Downloads: (external link)
https://cowles.yale.edu/sites/default/files/files/pub/d08/d0883.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cwl:cwldpp:883

Ordering information: This working paper can be ordered from
Cowles Foundation, Yale University, Box 208281, New Haven, CT 06520-8281 USA
The price is None.

Access Statistics for this paper

More papers in Cowles Foundation Discussion Papers from Cowles Foundation for Research in Economics, Yale University Yale University, Box 208281, New Haven, CT 06520-8281 USA. Contact information at EDIRC.
Bibliographic data for series maintained by Brittany Ladd ().