Draft:Binary paint shop problem

The binary paintshop problem is an operations research problem. Let $n\geq 1$ be an integer. The input is a word of length $2n$, with characters taken from an $n$-letter alphabet, in which each character appears exactly twice. Color the two occurrences of each character differently: one blue and one red.

The goal is to color the word while minimizing the number of color changes between adjacent letters.

For example, if $n=3$, the alphabet is $\{a,b,c\}$, and the word is abacbc. One possible coloring, in order, is blue, red, red, red, blue, blue. It has two color changes, which is the minimum for this example.

A presentation of the problem can be found in this paper.

The binary paintshop problem is a special case of a more general problem in which letters may appear different numbers of times and more than two colors may be used. In that general problem, no two occurrences of the same letter may receive the same color.

History

This problem comes from the early age of car factories. At the time, changing the painting color was an expensive and long part of the production. Therefore in the production line, one goal was to reduce the amount of changes, though it was possible to invert some of the models, this being complicated we restrain the possibility to have an easy modelisation.

Computational complexity

Brute-force algorithm

Each character has two possible assignments of blue and red to its two occurrences. Thus, there are $2^{n}$ possible colorings to consider. Given one such coloring, we can check its validity and count its color changes in $O(n)$ time. Exhaustive search therefore takes $O(n2^{n})$ time.

NP and certificates

A decision problem is in the class NP if every “yes” instance has a certificate of polynomial length that a deterministic algorithm can verify in polynomial time.

The decision version of the binary paintshop problem asks:

Given a word and an integer $k$, is there a valid coloring with at most $k$ color changes?

A certificate is a coloring of the word. To verify it, check that the two occurrences of each character have different colors, then count the color changes and check that their number is at most $k$. If the letters are indexed by an array, this takes time linear in the word length. Therefore, the decision problem is in NP.

An equivalent definition is that a decision problem is in NP if a non-deterministic Turing machine can decide it in polynomial time.

APX, PTAS, and APX-hardness

These definitions concern optimization problems. Assume that feasible solutions can be represented and checked in polynomial time and that their objective values can be computed in polynomial time.

For a minimization problem, an algorithm is a $c$-approximation if it returns a feasible solution of cost at most $c\operatorname {OPT}$, where $\operatorname {OPT}$ is the minimum possible cost and $c\geq 1$. For a maximization problem, it is a $c$-approximation if it returns a feasible solution of value at least $\operatorname {OPT} /c$.

APX

The class APX consists of the optimization problems that have a polynomial-time approximation algorithm with some fixed constant approximation factor.

PTAS

A polynomial-time approximation scheme (PTAS) is a family of algorithms with the following guarantee: for every fixed $c>1$, there is a polynomial-time algorithm that returns a $c$-approximation. The degree of the running-time polynomial may depend on $c$.

PTAS reduction

A PTAS reduction transforms instances and solutions of one optimization problem into instances and solutions of another while preserving arbitrarily accurate approximation.

A problem $A$ PTAS-reduces to a problem $B$ if, for every $\varepsilon >0$, there are polynomial-time procedures (for fixed $\varepsilon$) and a value $\delta (\varepsilon )>0$ such that:

1. An instance $x$ of $A$ is transformed into an instance $y$ of $B$.
2. Any $(1+\delta (\varepsilon ))$-approximate solution to $y$ can be transformed into a $(1+\varepsilon )$-approximate solution to $x$.

The reduction may choose the target accuracy $\delta$ as a function of the desired source accuracy $\varepsilon$.

APX-hardness

An optimization problem $B$ is APX-hard if every problem in APX PTAS-reduces to $B$. If $B$ had a PTAS, then every problem in APX would have a PTAS. Under the standard assumption $P\neq NP$, APX-hard problems therefore have no PTAS.

A problem is APX-complete if it is both APX-hard and in APX. APX-hardness is a stronger approximation-hardness result than NP-hardness.

NP-hardness of the binary paintshop problem

Bonsma, Epping, and Hochstättler proved that the decision version of the binary paintshop problem is NP-complete and that its optimization version is APX-hard.

APX-hardness of the binary paint shop problem

APX-hardness

Minimum vertex cover on cubic graphs is APX-hard.

Complexity under unique game conjecture

If the unique games conjecture is true one can show that there is no constant approximation algorithm in polynomial time for the binary paint shop problem, as one can reduce the Min UnCut Problem to the binary paint shop problem. Therefore one can only hope to use heuristic that holds on most instances, or that hold in probability assuming uniform distribution of words.

Algorithms

There exist some approximation algorithms.