Lin, Jyh-HanVitter, Jeffrey Scott2011-03-222011-03-221992J.-H. Lin and J. S. Vitter. “Nearly Optimal Vector Quantization via Linear Programming,” Proceedings of the 1992 IEEE Data Compression Conference (DCC ’92), Snowbird, UT, March 1992, 22–31. http://dx.doi.org/10.1109/DCC.1992.227479https://hdl.handle.net/1808/7237(c) 1992 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.We present new vector quantization algorithms based on the theory devel- oped in [LiV]. The new approach is to formulate a vector quantization problem as a 0-1 integer linear program. We rst solve its relaxed linear program by linear programming techniques. Then we transform the linear program solu- tion into a provably good solution for the vector quantization problem. These methods lead to the rst known polynomial-time full-search vector quanti- zation codebook design algorithm and tree pruning algorithm with provable worst-case performance guarantees. We also introduce the notion of pseudo- random pruned tree-structured vector quantizers. Initial experimental results on image compression are very encouraging.en-USArticle10.1109/DCC.1992.227479openAccess