Roy Schwartz: "Advances in Traffic Engineering and Discrepancy"

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.