<div dir="ltr"><div><div class="gmail_default" style="font-size:12.8px"><font face="tahoma, sans-serif" color="#000000">When:     Thursday, February 2nd at 11:00 am </font></div><div class="gmail_default" style="font-size:12.8px"><font face="tahoma, sans-serif" color="#000000"><br></font></div><div class="gmail_default" style="font-size:12.8px"><font face="tahoma, sans-serif" color="#000000">Where:    <span class="gmail-m_2953668934074478317gmail-m_-3155518689668024534m_9067904842688472155gmail-m_3071693547520408192gmail-il">TTIC</span>, 6045 S Kenwood Avenue, 5th Floor, Room 526</font></div><div class="gmail_default" style="font-size:12.8px"><font face="tahoma, sans-serif" color="#000000"><br></font></div><div style="font-size:12.8px"><span style="font-size:12.8px"><font color="#000000">Who:       Euiwoong Lee, CMU</font></span></div><div style="font-size:12.8px"><span style="font-size:12.8px"><font color="#000000"><br></font></span></div><div style="font-size:12.8px"><br></div></div><div style="font-size:12.8px">Title: Optimal Approximabilities beyond CSPs and Set Cover</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Abstract: <span style="font-size:12.8px">The last three decades have seen tremendous progress in both designing better approximation algorithms and proving their optimality. This success revealed optimal approximation ratios of many traditional combinatorial optimization problems such as Constraint Satisfaction Problems (CSPs) and Set Cover. </span></div><div style="font-size:12.8px"><div><br></div><div>My research has tried to expand the frontiers of approximation algorithms, with respect to the range of optimization problems as well as mathematical tools for algorithms and hardness. With the growth of computer science and its interaction with other scientific disciplines, new important optimization problems have emerged. They often have continuous domains or specialized structural properties, and are not easily captured by the traditional problems.</div><div><br></div><div>In this talk, I will describe three examples of my work called Graph Pricing, Polynomial Optimization, and Graph Transversal. They are motivated by various fields including internet economics, machine learning, quantum computing, and operations research. I will focus on connections between these new problems and fundamental combinatorial optimization problems, and how these connections enrich understanding of both classes.</div><div><br></div><div><br></div><div><br></div><div>Host: <a href="mailto:cjulia@ttic.edu">Julia Chuzhoy</a></div><div><br></div><div><br></div><div><br></div></div><div><div class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 504</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div>
</div>