Solving the p-Median Problem with Insights from Discrete Vector Quantization

Authors

Gino J. Lim, University of Houston - MainFollow
Allen Holder, Rose-Hulman Institute of TechnologyFollow
Josh Reese, PROS Revenue Management

Document Type

Article

Publication Date

8-11-2009

First Advisor

Allen Holder

Abstract

The goals of this paper are twofold. First, we formally equate the p-median problem from facility location to the optimal design of a vector quantizer. Second, we use the equivalence to show that the Maranzana Algorithm can be interpreted as a projected Lloyd Algorithm, a fact that improves complexity. Numerical results verify significant improvements in run-time.

Comments

MSTR 09-04

Recommended Citation

Lim, Gino J.; Holder, Allen; and Reese, Josh, "Solving the p-Median Problem with Insights from Discrete Vector Quantization" (2009). Mathematical Sciences Technical Reports (MSTR). 13.
https://scholar.rose-hulman.edu/math_mstr/13