Mathematics Commons^™

The Relationship Between Discrete Vector Quantization And The P-Median Problem, Allen G. Holder, G Lim, J Reese

Mathematics Faculty Research

We show that a well studied problem in the engineering community is the same as a problem studied by mathematical combinatorialists. Specifically, we show that the question of optimally designing a vector quantizer, which is an important problem in coding theory, is the same as the p-median problem, which is a classic graph theory problem with important applications in operations research. The importance of the relationship lies in the fact that both communities have spent years developing solution methodologies, and this connection permits each community to glean new ideas from the other. We show that two of the most popular …