Edge partitioning, i.e., partitioning the edges of an input graph into multiple parts, is a promising approach for processing large-scale graphs, especially for natural graphs whose degrees usually follow skewed power-law distributions. In this paper, we consider a basic edge partitioning problem named the minimum edge bisection (Min-Edge-Bisection) problem, i.e., given an undirected graph, partition the edges into two parts such that the sizes of the two parts are equal or differ by 1, referred to as edge bisection, such that the cost (i.e., the number of vertices with some incident edge in one part and some incident edge in the other part) is minimized. While the problem has been shown to be NP-hard, we go a step further and give some results about its approximability. In particular, we show that it is quite challenging to design a constant factor approximation algorithm for Min-Edge-Bisection even if it exists, in the sense that, the existence of such an algorithm would imply a constant factor approximation algorithm for the well known minimum bisection problem, whose existence or not has been an outstanding open problem in graph partitioning for several decades. We then propose a greedy algorithm for the problem with low time complexity. By analyzing the performance of this greedy algorithm, we further establish some interesting upper bounds on the cost of minimum edge bisection for both general graphs and power-law graphs.