Phasor measurement units (PMUs) are widely recognized to be instrumental for enhancing the power system situational awareness - a key step toward the future power grid. With limited PMU resources and high installation costs, it is of great importance to develop strategic PMU deployment methods. This paper focuses on optimally selecting PMU locations for monitoring transmission line status across the wide-area grid. To bypass the combinatorial search involved, a linear programming reformulation is first developed to provide an upper bound estimate for the global optimum. Furthermore, a greedy heuristic method is adopted with the complexity only linearly in the number of PMUs, while leveraging on the upper bound estimate a branch-and-bound algorithm is also developed to achieve a near-optimal performance at a reduced complexity. Numerical tests on various IEEE test cases demonstrate the validity of our proposed methods, greatly advocating the satisfactory performance the simple greedy method at only linear complexity. This suggests a hybrid method by using the greedy solution as a warm start to reduce the number of BB iterations.