Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs

Chen Wang, Chao Wang, Gregory Z. Gutin +1

Let $G=(V,E)$ be a graph and let each vertex of $G$ has a lamp and a button. Each button can be of ${\sigma }^{+}$-type or $\sigma$-type. Assume that initially some lamps are on and others are o…