Loading...
Please wait, while we are loading the content...
Similar Documents
Efficient array partitioning (1997).
| Content Provider | CiteSeerX |
|---|---|
| Author | Khanna, Sanjeev Muthukrishnan, S. Skiena, Steven |
| 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 O(np) [MS95]. In this paper, we present two improved algorithms for this problem: one runs in time O(n + p²(log n)²) and the other runs in time O(n log n). The former is optimal whenever p p n= log n, and the latter is nearoptimal for arbitrary p. We consider the natural generalization of this partitioning to two dimensions, where an n \Theta n array of items is to be partitioned into p² 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 t... |
| File Format | |
| Publisher Date | 1997-01-01 |
| Access Restriction | Open |
| Subject Keyword | Efficient Array Partitioning Maximum Weight Np-hard Gm96 Simple Proof Natural Generalization Theta Array Improved Algorithm Fact Np-hard |
| Content Type | Text |
