IEOR-DRO Seminar

[View Recording]

Title: A (slightly) Improved Approximation algorithm for Metric TSP

Abstract: In an instance of the (metric) traveling salesperson problem (TSP), we are given a list of n cities and their pairwise symmetric distances satisfying the triangle inequality, and we want to find the shortest tour that visits all cities exactly once and returns back to the starting point. I will talk about an algorithm that provably returns a tour whose cost is at most 50-eps percent more than the optimum where eps>0 is a small constant independent of n. This slightly improves classical algorithms of Christofides and Serdyukov from the 1970s. 

The proof exploits a deep connection to the rapidly evolving area of geometry of polynomials. In this area, we encode discrete phenomena, in our case uniform spanning tree distributions, in coefficients of complex multivariate polynomials, and we understand them via the interplay of the coefficients, zeros, and function values of these polynomials. Over the last fifteen years, this perspective has led to several breakthroughs in computer science such as construction of Ramanujan graphs and the Mihail-Vazirani's and Mason's conjectures for matroids. I will discuss how some of the ideas of this field can be used to design and analyze algorithms for TSP. 

Based on a joint work with Anna Karlin and Nathan Klein.

Bio: Shayan Oveis Gharan is an associate professor of the Paul Allen School of Computer Science and Engineering at University of Washington. He received his PhD from the MS&E department at Stanford University in 2013. Before joining UW he spent one and a half years as a postdoctoral Miller Fellow at UC Berkeley. Shayan's research exploits several tools in Mathematics such as theory of real stable and log-concave polynomials, and spectral graph theory to design and analyze (optimization) algorithms for discrete objects.

[View Recording]

Title: On Incorporating Forecast Information into MDPs

Abstract: In an increasing number of sequential decision-making applications, one has forecast information that can be used to enhance the decision process. In particular, in developing more efficient energy systems, one has the ability to use weather forecasts to improve the control of the associated system. In this talk, we will discuss ongoing work at Stanford that relates to the operation of Stanford’s district heating and cooling system, as well as a mathematical MDP formulation for linear control systems that takes into account forecast information in a principled way. By principled, we mean that the forecasts are required to be mathematically consistent with the underlying state dynamics, in the sense that the forecasts are required to satisfy a cerain martingale property. This work is joint with Jacques de Chalendar.

Bio: Peter W. Glynn is the Thomas Ford Professor in the Department of Management Science and Engineering (MS&E) at Stanford University, and also holds a courtesy appointment in the Department of Electrical Engineering. He was Director of Stanford's Institute for Computational and Mathematical Engineering from 2006 until 2010 and served as Chair of MS&E from 2011 through 2015. He is a Fellow of INFORMS and a Fellow of the Institute of Mathematical Statistics, and was an IMS Medallion Lecturer in 1995 and INFORMS Markov Lecturer in 2014. He was co-winner of the Outstanding Publication Awards from the INFORMS Simulation Society in 1993, 2008, and 2016, was a co-winner of the Best (Biannual) Publication Award from the INFORMS Applied Probability Society in 2009, was the co-winner of the John von Neumann Theory Prize from INFORMS in 2010, and gave the INFORMS Philip McCord Morse Lecture in 2020. In 2012, he was elected to the National Academy of Engineering. He was Founding Editor-in-Chief of Stochastic Systems and served as Editor-in-Chief of Journal of Applied Probability and Advances in Applied Probability from 2016 to 2018. His research interests lie in simulation, computational probability, queueing theory, statistical inference for stochastic processes, and stochastic modeling.

[View Recording]

Title: Research in Online Ad Markets: Automation, Robustness, and Learning

Abstract: We provide an overview of recent trends and future challenges in online ad markets with a focus on robustness, incentive-aware learning, and the auto-bidding world. In the first part,  we survey recent results and highlight challenges that emerge as the majority of advertisers adopt automatic bidding algorithms to bid on their behalf and the market transitions to the so-called auto-bidding world. As part of the move to more automation, we discuss (adversarial) robustness in designing online algorithms, learning, and pricing schemes. In particular, we present online learning algorithms that work under stochastic models with adversarial corruptions and describe recently developed algorithmic techniques that achieve the best of many worlds in a variety of online stochastic and adversarial models. Along the same lines, we discuss the design of dynamic mechanisms for repeated auctions that are robust to the presence of noise or imprecise forecasts. Next, we touch upon robustness in pricing, and explore incentive-aware learning algorithms for pricing in both dynamic and static auctions. Finally, we complement these results by exploring data-driven techniques to measure the extent to which bidders have incentives to strategize their bids in ad auctions.

Bio: Vahab Mirrokni is a distinguished scientist, serving as senior director for the New York and Zurich algorithms research groups at Google Research. He received his PhD from MIT in 2005 and his B.Sc. from Sharif University of Technology in 2001. He joined Google Research in 2008, after spending a couple of years at Microsoft Research, MIT and Amazon.com. He is the co-winner of paper awards at KDD'15, ACM EC'08, and SODA'05. His research areas include algorithms, distributed and stochastic optimization, and computational economics. The specific areas include Market Algorithms, Graph Mining, and Large-scale Optimization.

[View Recording: Part 1 & Part 2]

Title: Exactness in SDP Relaxations of Quadratically Constrained Quadratic Programs

Abstract: Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems. In a QCQP, we are asked to minimize a (possibly nonconvex) quadratic function subject to a number of (possibly

nonconvex) quadratic constraints. Such problems arise naturally in many areas of operations research, computer science, and engineering. Although QCQPs are NP-hard to solve in general, they admit a natural family of tractable convex relaxations.  In this talk, we will study the standard semidefinite program (SDP) relaxation for general QCQPs and examine when this relaxation is exact. By analyzing the "geometry" of the SDP relaxation, we will give both sufficient conditions and necessary conditions for different types of "exactness" conditions, and discuss a number of implications of these results for various applications.

This is joint work with Alex L. Wang and C.J. Argue.

Bio: Fatma Kılınç-Karzan is the Frank A. and Helen E. Risch Faculty Development Chair and Associate Professor of Operations Research at Tepper School of Business, Carnegie Mellon University. She holds a courtesy appointment at the Department of Computer Science as well.  She completed her PhD at Georgia Institute of Technology in 2011. Her research interests are on foundational theory and algorithms for convex optimization and structured nonconvex optimization, and their applications in optimization under uncertainty, machine learning and business analytics. Her work was the recipient of several best paper awards, including 2015 INFORMS Optimization Society Prize for Young Researchers and 2014 INFORMS JFIG Best Paper Award. Her research has been supported by generous grants from NSF and ONR, including an NSF CAREER Award.

Recording will be available here after the seminar date.

Title: TBA

Abstract: TBA

Bio: TBA

Recording will be available here after the seminar date.

Title: TBA

Abstract: TBA

Bio: TBA