Given any linear threshold function f on n Boolean variables, we construct a linear threshold function g which disagrees with f on at most an \in fraction of inputs and has integer weights each of magnitude at most \sqrt n? 2 x O(1/ \in^2). We show that the construction is optimal in terms of its dependence on n by proving a lower bound of O(\sqrt n) on the weights required to approximate a particular linear threshold function.