Optimum deployment of Relay Station (RS) is considered as the most important issue especially for the users near cell boundary. The Multi hop Relay (MHR) network introduces the RS for the purpose of extended coverage and increased throughput. The main objective of this work is to provide a better Quality of Service (QoS) with a minimum deployment cost. In this paper, we identify the candidate positions of RS that will achieve maximum system capacity. Based on the relay location, we propose two algorithms based on coverage and budget constraints. The simulation results indicate that the proposed algorithms achieved a reasonable coverage ratio within the budget constraint. © 2015 IEEE.