Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MINIMUM ARRAY PARTITION

• INSTANCE: An $n\times n$ array A of non-negative integers, and a positive integer p.
• SOLUTION: p-1 horizontal dividers $0=h_0<h_1<\cdots<h_p=n$ and p-1 vertical dividers $0=v_0<v_1<\cdots<v_p=n$ partitioning A into $p^2$ blocks.
• MEASURE:
  
  $$\max_{1\le i\le p\atop 1\le j\le p} \sum_{v_{i-1}<x\le v_i\atop h_{j-1}<y\le h_j} A[x,y].$$
  
  

  
  

• Good News: In APX [307].
• Bad News: Not approximable within less than 2 [205].
• Comment: The good news is valid also for generalizations to higher dimensions and other measures. The dual problem, where a limit $\delta$ is given instead of p, and where the problem is to find the minimum p such that the array can be partitioned into $p^2$ blocks where each block's measure is bounded by $\delta$, is approximable within $O(\log n)$ [307].