Collaborative Research: AF: Medium: Design and Analysis of Models and Algorithms for Real-life Problems

Toyota Technological Institute At Chicago, Chicago IL

Investigators

Abstract

Recent years have seen a dramatic rise in applications of computer and data science in business, engineering, healthcare, and science. People use computers for analyzing increasingly large amounts of data and solving progressively more difficult problems. Processing growing amounts of data and solving increasingly hard problems require new high-performance algorithms. This project will explore new promising directions in algorithm design with the aim of developing efficient algorithms that are tailored to working with real-life data. To this end, the investigators will study the structure of real-life problems, analyze hidden patterns in the data, and create new mathematical and statistical models of real-world problems. They will use their findings to improve existing algorithms and develop new, highly efficient ones. The investigators will ensure that the new algorithms are "software developer-friendly": these algorithms will be fast and easy to implement, and will rely on existing technologies. The project will focus on computational problems that arise in machine learning, operations research, and discrete optimization. It will advance understanding of the nature of real-life problem instances, by identifying properties that distinguish them from worst-case instances (which rarely or never appear in practice) and designing better algorithms (with provable performance guarantees) for them. It will provide a (partial) answer to fundamental theoretical questions: Why do many heuristics for computationally hard problems work well in practice? And how can one design and formally analyze algorithms for real-life problem instances? To answer these questions, the team of investigators will create new models for real-life data, develop new algorithms, and introduce new mathematical techniques for analyzing these algorithms. The results will be relevant to researchers and practitioners in machine learning, optimization, and other areas; in particular, the results will provide them with new practical algorithms. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.