Wireless broadband networks, especially WiMAX networks, have emerged in the industry recently and many challenging research issues arise. In this paper, we proposed a heuristic clustering algorithm for minimum cost wireless broadband overlay network deployment. Moreover, we also modified and implemented two heuristic algorithms based on classic linear programming based capacitated facility location algorithms. We analyzed the theoretical worst-case performance ratio of our algorithm and our numerical results showed that our algorithm performs much better in practical network settings.