Live multimedia streaming over the Internet has steadily gained popularity over the past decade - primarily fueled by the growth in the available network bandwidth and rich multimedia applications. Various approaches to support live multimedia streaming can be broadly categorized into two alternatives, namely, IP multicast based and overlay based. While IP multicast based solution is dependent on the availability of IP multicast enabled network, peer-to-peer approach does not require any changes at the the network layer. However in a peer-to-peer based approach, peers frequently join and leave the system which often results in service disruptions, hence degradation of the overall quality and reputation of the services. In this situation, a hybrid approach is considered as a viable alternative where the service providers deploy multiple proxies all over the Internet and make them constitute a core tree in the peer-to-peer system. The proxies behave as stable nodes that are always in the system in spite of the frequent join and leave of the ordinary peers. In the hybrid approach, the main issue is the construction of the core tree that maximizes the overall quality of the system. The locations of the proxies as well as the topology formed by the proxies affect the performance due to the real time requirements in a live streaming. In this paper, we propose a centralized core tree construction scheme based on various optimization algorithms. Our proposed method provides a general framework to obtain a tree for arbitrary performance metrics. Furthermore, we show that our optimization based approaches can provide a better core tree than some greedy heuristic approaches such that the average delay from the source to each proxy decreases by 20-40%. © 2010 IEEE.