In modern broadband mesh networks, communication between two end nodes is carried out not directly, but through a number of intermediate nodes. While these nodes’ only function may be to relay information from one point to another, they may also host computational elements which perform some service on behalf of other applications. We deal with the problem of optimally mapping multimedia content transcoding service elements onto network resources. There may be several places in the network where the required compression and decompression services could be performed. We would like to select the best locations that meet the application’s requirements. We propose a new approximation algorithm for constrained path optimization, which provides better scalability and simplicity than previous approaches. This is accomplished basically by partitioning the overall problem into smaller ones.