Largest Volume Inscribed Rectangles in Convex Sets Defined by Finite Number of Inequalities
研究在有限个凸不等式定义的紧凸集中，寻找最大体积（轴对齐）内接矩形的问题，提出了优化模型和几何方法，包括内点法算法和二维参数化优化方法，并给出了改进的子线性时间近似算法。
This paper considers the problem of finding maximum volume (axis-aligned) inscribed boxes in a compact convex set, defined by a finite number of convex inequalities, and presents optimization and geometric approaches for solving them. Several optimization models are developed that can be easily generalized to find other inscribed geometric shapes such as triangles, rhombi, and squares. To find the largest volume axis-aligned inscribed rectangles in the higher dimensions, an interior-point method algorithm is presented and analyzed. For two-dimensional space, a parametrized optimization approach is developed to find the largest area (axis-aligned) inscribed rectangles in convex sets. The optimization approach provides a uniform framework for solving a wide variety of relevant problems. Finally, two computational geometric [Formula: see text]–approximation algorithms with sublinear running times are presented that improve the previous results. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: The author is grateful for the support of Northeastern University for this research. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0239 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0239 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .