Media mapping in video-on-demand server networks is a new combinatorial optimization problem. The network of video servers can be implemented on the top of a closely connected network of workstations or on a wide area network of servers. This paper addresses the media mapping problem, taking the user access patterns, overall storage capacity and communication bandwidth limitations of the server network into account. A number of methods based on local search algorithms for the solution of the mapping problem are proposed and verified by use of a set of benchmark problems. The simulations show that these heuristic solutions can achieve nearly optimal solutions in a short computational time.