Finding the Largest l(p)-Ball in a Polyhedral Set.
Abstract
A simple linear programming formulation is given for finding a ball or hypercube with largest radius contained in a polyhedral set defined by m linear inequalities. The linear program also has m linear constraints similar to those defining the set. It is shown that finding the largest ball is not much more difficult than finding a feasible point. When the center of ball is fixed, the largest radius is easily obtained as the smallest of m ratios. The results can be extended to balls defined by other norms such as elliptic norms. Keywords: Linear programming, Polyhedral set, Norm, Computational complexity, and Hypercube.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1984
- Accession Number
- ADA153542
Entities
People
- T. H. Shiau
Organizations
- University of Wisconsin–Madison