Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

Where should we locate grocery stores to best eliminate food deserts? Questions like this motivate the problem of equitable facility location, which seeks to distribute facilities in a way that benefits the many without ignoring the few.  This is typically solved using an exact integer program minimizing a given inequity metric.  We prove that graphical designs provide a polynomial time constant factor approximation algorithm for equitable facility location. A graphical design is a quadrature rule for a graph — that is, a subset of vertices that totally understands low complexity functions on the graph.  We show how the combinatorics of these graphical designs guarantees their existence, and further that they can be found by a linear program.  We demonstrate the power of this technique, which is undersold by the approximation algorithm, compared to other methods on real world US Census data of cities across the country. Primarily based on upcoming work with Jawhara Emhemed, Drew Horton, and Emily Speakman