## Abstract

We consider the problem of partitioning an array of n items into p intervals so that the maximum weight of the intervals is minimized. The currently best known bound for this problem is 0(n+p^{1+ε}) [HNC92] for any fixed ε< 1. In this paper, we present an algorithm that runs in time O(n log n); this is the fastest known algorithm for arbitrary p. We consider the natural generalization of this partitioning to two dimensions, where an nxn array of items is to be partitioned into p^{2}blocks by partitioning the rows and columns into p intervals each and considering the blocks induced by this partition. The problem is to find that partition which minimizes the maximum weight among the resulting blocks. This problem is known to be NP-hard [GM96]. Independently, Charikar et, al. have given a simple proof that shows that the problem is in fact NP-hard to approximate within a factor of two. Here we provide a polynomial time algorithm that determines a solution at most O(1) times the optimum; the previously best approximation ratio was O(√p) [HM96], Both the results above are proved for the case when the weight of an interval or block is the sum of the elements in it. These problems arise in load balancing for parallel machines and data partitioning in parallel languages. Applications in motion estimation by block matching in video and image compression give rise to the dual problem, that of minimizing the number of dividers p so that the maximum weight of a block is at most S. We give an O(log n) approximation algorithm for this problem. All our results for two dimensional array partitioning extend to any higher fixed dimension.

Original language | English (US) |
---|---|

Title of host publication | Automata, Languages and Programming - 24th International Colloquium, ICALP 1997, Proceedings |

Editors | Pierpaolo Degano, Roberto Gorrieri, Alberto Marchetti-Spaccamela |

Publisher | Springer Verlag |

Pages | 616-626 |

Number of pages | 11 |

ISBN (Print) | 3540631658, 9783540631651 |

DOIs | |

State | Published - 1997 |

Externally published | Yes |

Event | 24th International Colloquium on Automata, Languages and Programming, ICALP 1997 - Bologna, Italy Duration: Jul 7 1997 → Jul 11 1997 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1256 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 24th International Colloquium on Automata, Languages and Programming, ICALP 1997 |
---|---|

Country/Territory | Italy |

City | Bologna |

Period | 7/7/97 → 7/11/97 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)