On optimal cuts of hyperrectangles
| Autor: | Viet Hai Nguyen, Fabrizio d'Amore, Thomas Roos, Peter Widmayer |
|---|---|
| Rok vydání: | 1995 |
| Předmět: |
Numerical Analysis
Computer Science Applications Theoretical Computer Science Combinatorics Computational Mathematics Hyperrectangle Computational Theory and Mathematics Hyperplane Partition (number theory) Rectangle Linear combination Computer communication networks Software Cutting-plane method Mathematics |
| Zdroj: | Computing. 55:191-206 |
| ISSN: | 1436-5057 0010-485X |
| Popis: | We are given a set ofn d-dimensional (possibly intersecting) isothetic hyperrectangles. The topic of this paper is the separation of these rectangles by means of a cutting isothetic hyperplane. Thereby we assume that a rectangle which is intersected by the cutting plane iscut into two non-overlapping hyperrectangles. We investigate the behavior of several kinds of balancing functions, as well as their linear combination and present optimal and practical algorithms for computing the corresponding balanced cuts. In addition, we give tight worst-case bounds for the quality of the balanced cuts. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink