REU Student	Graduate Mentor	Faculty Advisor
Lindsey Bleimes	Charlie Garrod	Adam Meyerson

We are attempting to find fast, accurate algorithms for the facility location problem. Generally stated, the goal is to select locations which are "near" to most of a given set of data points. This problem has wide-ranging applications in operations research (selecting locations for warehouses) and in computer science (clustering of large databases, placement of routers in a network).

The problem can be modeled using integer programming and solved exactly for moderately sized instances. However for large instances or situations where facility location is a subroutine in another network design problem, the running time of integer programs can be prohibitive. There has been a great deal of research into combinatorial approaches to the problem (for example local search algorithms) and approaches which work on very large databases using streaming models. This previous work is theoretical in nature, proving worst-case approximation guarantees of, at best, 1.52.

This project aims to measure the performance of combinatorial approaches on realistic problem instances. We hope to show that these techniques will perform better than their worst-case bounds and provide viable alternatives to integer programming for time-sensitive applications.

Preliminary Presentation (ppt), (pdf)

Other Mini-PROBEs for Summer 2003

Anonymous Communication
Designing Overlay Multicast Networks for Streaming
Dynamic Algorithms
HumanAUT
Moving Mesh Simulations
Space-Efficient Point Location