Multipass Linear Sketches for Geometric LP-Type Problems

N. Efe Çekirge, William Gay, David P. Woodruff

LP-type problems such as the Minimum Enclosing Ball (MEB), Linear Support Vector Machine (SVM), Linear Programming (LP), and Semidefinite Programming (SDP) are fundamental combinat…