File LinearPartition.h

↰ Parent directory (ADS/optimization)

The linear partition problem (also the painter’s partition, or the bottleneck partition of a chain): the items A[ 0 .

Definition (ADS/optimization/LinearPartition.h)

Detailed Description

. n - 1 ] split into k contiguous parts so that the largest sum of a part is the least, e.g. n boards of lengths A_i to be painted by k painters, each one a block of consecutive boards, in the least time.

  • linearPartition() solves it for items of any sign and exactly k nonempty parts by the dynamic programming on the prefix sums S, :math:` D[ t ][ i ] = min_{t - 1 leq j < i} max( D[ t - 1 ][ j ] , S[ i ] - S[ j ] ) , :math: D[ 1 ][ i ] = S[ i ] `, with the best cut kept for each entry; O( k n^2 ) time and O( k n ) space.

  • painterPartition() solves it for integer items not negative and at most k parts by a binary search on the answer x: the greedy that closes a part only when the next item does not fit in x uses the fewest parts, so x is feasible iff the greedy needs at most k of them; :math:` O( n log sum_i A_i ) ` time and O( 1 ) space. With items not negative and k <= n, at most k parts and exactly k nonempty ones give the same value.

In the literature, the problem on a chain of n items is solved in O( n ) time for k fixed, and in :math:` O( n + k^2 log^2 n ) ` in general, by parametric search on the prefix sums (Frederickson); the dynamic programming above has the quadrangle inequality, so that the monotone cuts of Knuth and Yao bring it to O( k n ) for items not negative.

The contracts [see File Contract.h]: 1 <= k <= n for linearPartition(), and its cuts give the cost found (checked at level 3); k >= 1 and the items not negative for painterPartition(). The functions are defined in LinearPartition.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 13, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

    1. Skiena, The Algorithm Design Manual, 3rd ed., Springer, 2020, section 10.7

    1. Frederickson, Optimal algorithms for tree partitioning, Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms, 168-177, 1991

    1. Yao, Efficient dynamic programming using quadrangle inequalities, Proc. 12th ACM Symposium on Theory of Computing, 429-435, 1980, doi:10.1145/800141.804691

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions