Given a bipartite graph G=(V,W,E), a 2-layered drawing consists of placing nodes in the first node set V on a straight line L_1 and placing nodes in the second node set W on a parallel line L_2.  For a given ordering of nodes in W on L_2, the one-sided crossing minimization problem asks to find an ordering of nodes in V on L_1 so that the number of arc crossings is minimized.  A well known lower bound LB on the minimum number of crossings is obtained by summing up min{c_{uv},c_{vu}} over all node pairs u,v in V, where c_{uv} denotes the number of crossings generated by arcs incident to u and v when u precedes v in an ordering. In this talk, we prove, by a probabilistic method, that there exists a solution whose crossing number is at most 1.4664LB, and that there exits a solution whose crossing number is at most (1.2964+12/(delta-4))LB if the minimum degree delta of a node in V is at least 5.  Such solutions can be obtained deterministically by derandomized algorithms.