On a 2-dimensional equipartition problem |
| |
| Affiliation: | 1. Department of Kinesiology, University of Waterloo, Waterloo, ON, Canada;2. School of Kinesiology, University of British Columbia, Vancouver, BC, Canada;3. International Collaboration on Repair Discoveries, University of British Columbia, Vancouver, BC, Canada;4. Djavad Mowafaghian Centre for Brain Health, University of British Columbia, Vancouver, BC, Canada;5. Department of Kinesiology, Brock University, St. Catharines, ON, Canada;6. Department of ORL, University Hospital Basel, Basel, Switzerland;1. Università degli Studi di Milano – Bicocca, Department of Earth and Environmental Sciences (DISAT), P.zza della Scienza 1, 20126 Milano, Italy;2. Politecnico di Milano, Department of Civil and Environmental Engineering (DICA), P.zza L. da Vinci 32, 20133 Milano, Italy |
| |
| Abstract: | The present paper deals with the following problem, which arises in a variety of applications: given a node-weighted rectangular grid graph, perform p horizontal full cuts and q vertical ones so as to make the weights of the resulting (p+1)(q+1) rectangular subgrids “as close as possible”. Computational complexity aspects are discussed. Several heuristic algorithms for obtaining partitions which minimize the maximum weight of a subgrid are developed, and computational results are reported. Theoretical bounds on the approximation error are also given. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
