Title: Combinatorial Optimization - From Theory to Practice
Dr. Roy Schwartz - Department of Computer Science- Princeton University.
Abstract:
In this talk I will present two examples of the practicality of theoretical techniques in combinatorial optimization.
First, I will consider the problem of routing transfers in wide area networks.
Long running transfers are usually time critical, as delays might impact service quality, affect customer revenue, and increase costs incurred by waste of resources.
Current traffic engineering systems fall short as they do not provide pre-facto guarantees on such long running transfers.
I will present an online traffic engineering system that provides pre-facto guarantees while maximizing both fairness and network utility.
The system is based on theoretical algorithmic techniques for solving packing and covering linear programs, and can quickly handle an evolving linear program containing up to millions of variables and constraints.
Second, I will consider the problem of unconstrained maximization of a submodular function.
This problem is one of the most basic submodular optimization problems and it has a wide range of applications both in practice and theory.
Additionally, the massive size of data in recent years requires any practical algorithmic solution for this problem to be extremely simple and fast.
I will present a simple randomized adaptation of the greedy algorithm which provides an information-theoretic guarantee.
This solution also runs in linear time, rendering it practical (and indeed since its introduction our algorithm has been used in practice in various settings).
Roy Schwartz is currently a postdoctoral research associate at the Department of Computer Science in Princeton University.
Formerly, he was a postdoctoral researcher at Microsoft Research.
Roy did his Ph.D. at the Technion under the supervision of Prof. Seffi Naor.
His research focuses on combinatorial optimization and the design and analysis of algorithms, including:
approximation algorithms and coping with NP-hardness, the geometry of metric spaces and its applications, submodular optimization, and randomized algorithms.
A special emphasis is given on the combination of the above with probability and stochastic processes, continuous optimization and combinatorics.
Roy's work deals both with fundamental algorithmic problems as well as applications that arise in other settings such as networking, scheduling, and machine learning.
ההרצאה תתקיים ביום חמישי, 11.12.14, בשעה 12:00 בחדר 206, בנין וולפסון הנדסה, הפקולטה להנדסה, אוניברסיטת תל-אביב.
