Eventshttp://www.orie.cornell.eduEventsWed, 23 Aug 2017 15:17:32 -0400Joint ORIE Colloquium - CS Theory Seminar: Laci Vegh (London School of Economics) - A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow MaximizationGeneralized flows are a classical extension of network flows, where the flow gets multiplied by a certain gain or loss factor while traversing an arc. This is a widely applicable model, as the factors can be used to model physical changes such as leakage or theft; or alternatively, they can represent conversions between different types of entities, e.g. different currencies. In the talk, I present a new strongly polynomial algorithm for generalized flow maximization. Besides improving on the running time of the previous strongly polynomial algorithm by a factor O(n^2), the algorithm is also substantially simpler. This is joint work with Neil Olver (VU Amsterdam).http://www.orie.cornell.edu/news/seminars/orie_colloquium.cfm?event=18097
http://www.orie.cornell.edu/news/seminars/orie_colloquium.cfm?event=18097
Mon, 28 Aug 2017 16:00:00 -0400Joint ORIE Colloquium - CS Theory Seminar: Laci Vegh (London School of Economics) - A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman ProblemWe give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem. This is joint work with Ola Svensson and Jakub Tarnawski (EPFL).http://www.orie.cornell.edu/news/seminars/orie_colloquium.cfm?event=18098
http://www.orie.cornell.edu/news/seminars/orie_colloquium.cfm?event=18098
Tue, 29 Aug 2017 16:15:00 -0400ORIE Colloquium: Itai Ashlagi (Stanford)Title/abstract TBAhttp://www.orie.cornell.edu/news/seminars/orie_colloquium.cfm?event=18019
http://www.orie.cornell.edu/news/seminars/orie_colloquium.cfm?event=18019
Tue, 12 Sep 2017 16:15:00 -0400ORIE Colloquium: Mengdi Wang (Princeton)Title/abstract TBAhttp://www.orie.cornell.edu/news/seminars/orie_colloquium.cfm?event=18015
http://www.orie.cornell.edu/news/seminars/orie_colloquium.cfm?event=18015
Tue, 19 Sep 2017 16:15:00 -0400ORIE Colloquium: Sanjay Shakkottai (UT Austin) - Identifying Best Interventions through Online Importance SamplingMotivated by applications in computational advertising and systems biology, we consider the problem of identifying the best out of several possible soft interventions at a source node V in an acyclic causal directed graph, to maximize the expected value of a target node Y (located downstream of V ). Our setting imposes a fixed total budget for sampling under various interventions, along with cost constraints on different types of interventions. We pose this as a best arm identification bandit problem with K arms where each arm is a soft intervention at V, and leverage the information leakage among the arms to provide the first gap dependent error and simple regret bounds for this problem. Our results are a significant improvement over the traditional best arm identification results in this setting. We empirically show that our algorithms outperform the state of the art in a Flow Cytometry data-set, and also apply our algorithm for model interpretation of the Inception-v3 deep net that classifies images. This is based on joint work with Rajat Sen, Karthikeyan Shanmugam, and Alex Dimakis. Bio: Sanjay Shakkottai received his Ph.D. from the ECE Department at the University of Illinois at Urbana-Champaign in 2002. He is with The University of Texas at Austin, where he is currently the Ashley H. Priddy Centennial Professor in Engineering, the Director of the Wireless Networking and Communications Group (WNCG), and a Professor in the Department of Electrical and Computer Engineering. He received the NSF CAREER award in 2004, and was elected as an IEEE Fellow in 2014. His research interests lie at the intersection of algorithms for resource allocation, statistical learning and networks, with applications to wireless communication networks and online platforms/marketplaces.http://www.orie.cornell.edu/news/seminars/orie_colloquium.cfm?event=18099
http://www.orie.cornell.edu/news/seminars/orie_colloquium.cfm?event=18099
Tue, 03 Oct 2017 16:15:00 -0400