Time+Place: Monday 22/12/2014 11:00 Room 337-8 Taub Bld.
Title: Advances in Traffic Engineering and Discrepancy
Speaker: Roy Schwartz - CS-Lecture - REVISED - NOTE UNUSUAL DAY AND TIME http://www.cs.princeton.edu/~roysch/
Affiliation: Department of Computer Science, Princeton University.
Host: Seffi Naor

Abstract:


I will discuss two recent works:
1. Long running transfers in wide area networks 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.
2. Combinatorial discrepancy is a basic problem in computer science and 
combinatorics, that has applications in diverse areas such as: 
computational geometry, complexity theory, Monte-Carlo simulation, 
number theory and more.
Given a family of subsets S_1,\ldots,S_n of a universe N of size n, the 
goal is to color the elements of N by one of two colors {-1,+1} such 
that each set is colored as evenly as possible.
Spencer's well known theorem asserts that this can be done while keeping 
the absolute value of the sum of the colors of every set to be 
O(\sqrt{n}).
Known proofs, algorithmic and existential, recursively construct 
"partial colorings", which assign colors only to half the universe N.
Unfortunately, this approach fails to provide tight guarantees to other 
important discrepancy problem, e.g., the Beck-Fiala and Koml\'os 
conjectures.
Therefore, it has been an open question to find new techniques that 
avoid partial colorings.
In this work I will present the first algorithm that directly computes a 
full coloring.
The algorithm is based on a geometric perspective and in its core is the 
analysis of ellipsoids contained in polytopes.

Short Bio:
Roy Schwartz is currently a postdoctoral research associate at the 
Department of Computer Science in Princeton University.
Formerly, he was a postdoctoral researcher at the Theory Group at 
Microsoft Research.
Roy did his Ph.D. at the Technion under the supervision of Prof. Seffi Naor.
His research focuses on the design and analysis of algorithms and 
combinatorial optimization, 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.