In most cases today, image palettization consists of reducing the overall number of colors in an image to some fixed number globally. This is typically solved as a straightforward but computationally difficult clustering problem.
A more difficult version of this problem involves older graphics hardware where the palette is broken down into N subpalettes (e.g. of 4 colors each) and the image is broken down into XxY-pixel tiles where each tile can only use colors from a single subpalette and N << the number of tiles. Here both the exact colors, the arrangement of colors into subpalettes, and the subpalette for each tile of the image are all unknowns that must be solved together.
How could this more difficult problem be solved, algorithmically?