problem as a total cost MDP with uncountable state space and non-compact action sets. We prove the existence of an optimal policy and convergence of value iteration (Theorem \[theorem:convergence\_of\_value\_iteration\]); these results for uncountable state space and non-compact action space are not evident from standard literature. We study properties of the value function analytically. This is the first time that the as-you-go deployment problem is formulated to maximize the end-to-end data rate under the full-duplex multi-relay channel model.

-   [**Numerical Results on As-You-Go Deployment:**]{} In Section \[section:numerical\_work\_information\_theoretic\_model\], we study the policy structure numerically. We also demonstrate numerically that the proposed as-you-go algorithm achieves an end-to-end data rate sufficiently close to the maximum possible achievable data rate for offline placement. This is particularly important since there is no other benchmark in the literature, with which we can make a fair comparison of our policy.

-   The material in Section \[sec:mdp\_total\_power\] and Section \[section:numerical\_work\_information\_theoretic\_model\] were absent in the conference version [@chattopadhyay-etal12optimal-capacity-relay-placement-line].

Organization of the Paper
-------------------------

In Section \[sec:system\_model\_and\_notation\], we describe our system model and notation. In Section \[sec:total\_power\_constraint\], we address the problem of relay placement on a line of known length. Section \[sec:mdp\_total\_power\] deals with the problem of as-you-go deployment along a 