Abstract:
We study geometric bodies that appear in data analysis. First, we consider clustering for land consolidation. The optimal assignment of lots to farmers can be modelled as approximate norm-maximization. This leads to provably good algorithms generalizing classical methods in machine learning. Second, we study the combinatorial diameter of the relevant polyhedra. This leads us to the circuit diameters, which provide lower bounds on the number of steps of augmentation algorithms along circuits.