From discrete to continuous and back: modern algorithmic techniques for some classical problems in optimization

Abstract: Larger datasets and modern computing systems have shifted the focus in algorithm design to faster and/or distributed algorithms that still retain strong theoretical guarantees. A recurring theme in this line of work is the interplay of techniques from continuous and discrete optimization to design more scalable algorithms. We examine two classical problems from my own experience through this modern algorithmic lens.

First, we consider metric TSP, a central problem in combinatorial optimization that has historically inspired many techniques. We show how to approximate the underlying linear program in nearly-linear time in the input size. We then show how to leverage the LP solution and compute an approximate tour an order of magnitude faster than previously known. (The latter running time is also nearly linear for explicit metrics.) We will also discuss a more general framework for approximating other LPs of interest in nearly linear time, by a careful combination of discrete and continuous techniques.

In the second part of the talk, we will discuss parallel algorithms for constrained submodular maximization. Submodular maximization generalizes many problems in combinatorial optimization and has applications in machine learning and data mining. Scalable algorithms are increasingly important for these applications. We derive parallel algorithms with only a polylogarithmic number of parallel rounds for a variety of constraints including packing constraints and matroid constraints. These algorithms were developed by first taking a certain continuous viewpoint of submodular functions that I plan to discuss, which leads to clean and intuitive algorithms.

Biography: Kent Quanrud is a Ph.D. candidate in Computer Science at the University of Illinois at Urbana-Champaign, advised by Chandra Chekuri and Sariel Har-Peled. His research is in the design and analysis of algorithms, with interests ranging from classical topics such as combinatorial optimization and approximation algorithms to modern paradigms such as nearly linear time approximation algorithms and the interplay between discrete and continuous optimization.

 

Share this event:

facebook linked in twitter email

Media Contact: Antonio Blanca

 
 

About

The School of Electrical Engineering and Computer Science was created in the spring of 2015 to allow greater access to courses offered by both departments for undergraduate and graduate students in exciting collaborative research in fields.

We offer B.S. degrees in electrical engineering, computer science, computer engineering and data science and graduate degrees (master's degrees and Ph.D.'s) in electrical engineering and computer science and engineering. EECS focuses on the convergence of technologies and disciplines to meet today’s industrial demands.

School of Electrical Engineering and Computer Science

The Pennsylvania State University

207 Electrical Engineering West

University Park, PA 16802

814-863-6740

Department of Computer Science and Engineering

814-865-9505

Department of Electrical Engineering

814-865-7667