Abstract: The problem of efficiently mapping a virtual network (VN) over a common physical network is very important for the network virtualization. This paper proposes a VN mapping algorithm based on the relaxed mixed integer linear program (MILP) with close coordination between the node and link mapping. The integer constraints in the MILP formulation of VN mapping problem are relaxed and new linear constraints are added to obtain a strict LP relaxation model, called STRICT_LP. And then a heuristic algorithm is devised to progressively solve the STRICT_LP to get the whole mapping solution. The simulation results show that the proposed algorithm can realize a better coordination between node and link mapping stages and the performances are better than D-ViNE and R-ViNE in term of the acceptance ratio, revenue, cost, and the ratio of revenue to cost.