  In this paper, we present a new approach to linearizing zero-one quadratic
minimization problem which has many applications in computer science and
communications. Our algorithm is based on the observation that the quadratic
term of zero-one variables has two equivalent piece-wise formulations, convex
and concave cases. The convex piece-wise objective function and/or constraints
play a great role in deducing small linearization. Further tight strategies are
also discussed.
