In this paper, we explore the small-cell uplink access point (AP) placement problem in the context of throughput-optimality and provide solutions while taking into consideration inter-cell interference. First, we briefly review the vector quantization (VQ) approach and related single user throughput-optimal formulations for AP placement. Then, we investigate the small-cell case with multiple users and expose the limitations of mean squared error based VQ for solving this problem. While the Lloyd algorithm from the VQ approach is found not to strictly solve the small-cell case, based on the tractability and quality of resulting AP placement, we deem it suitable as a simple and appropriate framework to solve more complicated problems. Accordingly, to minimize ICI and consequently enhance achievable throughput, we design two Lloyd-type algorithms, namely, the Interference Lloyd algorithm and the Inter-AP Lloyd algorithm, both of which incorporate ICI in their distortion functions. Simulation results show that both of the proposed algorithms provide superior 95\%-likely rate over the traditional Lloyd algorithm and the Inter-AP Lloyd algorithm yields a significant increase of up to 36.34\% in achievable rate over the Lloyd algorithm.