random length. This paper extends our previous work in [@chattopadhyay-etal12optimal-capacity-relay-placement-line], which presents the analysis for the case of given $L$ and $N$; the study under given $L$ and $N$ is a precursor to the formulation of as-you-go deployment problem, since it motivates an additive cost structure that is essential for the formulation of the sequential deployment problem as a Markov decision process (MDP).

The deploy-as-you-go problem has been addressed by previous researchers. For example, Howard et al., in [@howard-etal02incremental-self-deployment-algorithm-mobile-sensor-network], provide heuristic algorithms for incremental deployment of sensors in order to cover a deployment area. Souryal et al., in [@souryal-etal07real-time-deployment-range-extension], propose heuristic deployment algorithms for the problem of impromptu wireless network deployment, with an experimental study of indoor RF link quality variation. The authors of [@bao-lee07rapid-deployment-ad-hoc-backbone] propose a collaborative deployment method for multiple deployment agents, so that the contiguous coverage area of relays is maximized subject to a total number of relays constraint. However, until the work in [@mondal-etal12impromptu-deployment_NCC] and [@sinha-etal12optimal-sequential-relay-placement-random-lattice-path], there appears to have been no effort to rigorously formulate as-you-go deployment problem in order to derive optimal deployment algorithms. The authors of [@mondal-etal12impromptu-deployment_NCC] and [@sinha-etal12optimal-sequential-relay-placement-random-lattice-path] used MDP based formulations to address the problem of placing relay nodes sequentially along 