On a 2-dimensional equipartition problem

✍ Scribed by Francesco Conti; Federico Malucelli; Sara Nicoloso; Bruno Simeone

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 192 KB
• Volume: 113
• Category: Article
• ISSN: 0377-2217
• DOI: 10.1016/s0377-2217(97)00429-3

✦ Synopsis

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 1q 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.