On 15-19 February 2016 NETWORKS organizes the second Training Week for PhD Students. The topics of this Training Week are optimization and approximation and stochastic networks.

 

About Training Weeks

One of the exciting aspects of NETWORKS is that it covers stochastic and algorithmic
aspects of networks. This provides a unique opportunity to educate young researchers in both
areas. To reach that goal, NETWORKS organizes Training Weeks. Each training week will combine two topics, one from stochastics and one from algorithmics. The training weeks will be held off-campus, so that they also serve as community-building activities.

 

Target group

All NETWORKS PhD students are expected to participate in these Training Weeks, but other researchers from NETWORKS are very welcome as well.

For participants of NETWORKS it is possible to subscribe against a fee of € 600,00. If you are interested please send an email to: info@thenetworkcenter.nl.

 

Optimization and Approximation

 

The lectures on Optimization and Approximation are taught by Lex Schrijver and Gerhard Woeginger.

 

               

Lex Schrijver                     Gerhard Woeginger
(Optimization)                   (Approximation)

 

Topic 1: Network algorithmics for paths, flows, and arborescences

We discuss the basic network optimization algorithms, starting with shortest path, maximum flow, minimum-cost flow, and shortest tree, and proceeding to shortest and disjoint arborescences, optimum matching, and minimum feedback arc sets. We also go into the geometric and duality aspects of optimization problems and their algorithms.

 

Topic 2: Network decomposition and graph limits

We explain and prove "Szemerédi's lemma", stating that each network can be decomposed into a finite number of almost equal-sized parts such that between almost every two parts the connections are almost uniformly distributed. Here the finite number depends only on how close `almost' is taken, and does not depend on the size of the network. We discuss applications of the lemma and we go into its consequences for the existence of graph limits - structures that represent converging sequences of networks.

 

Topic 3: Approximation from relaxations

We discuss approaches to approximability that are based on rounding an underlying linear programming relaxation. We analyze the resulting approximation algorithms, intergrality gaps, and worst case instances.

 

Topic 4: Approximation schemes

We surveys general methods for deriving polynomial time approximation schemes. All these methods are based on rounding and enumeration methods, sometimes combined with dynamic programming or integer programming formulations. Moreover, we will discuss how to disprove the existence of a scheme (under P not equal NP).

 

Stochastic Networks

 

The lectures on Stochastic Networks are taught by Sem Borst and Johan van Leeuwaarden.

 

               

Johan van Leeuwaarden        Sem Borst

(Stochastic Networks)          (Stochastic Networks)

 

The material will be based on lecture notes, the book Stochastic Networks by Frank Kelly and Elena Yudovina and several research papers of Johan and Sem written together with graduate students.

 

Communication networks are the arteries of today's society, create large-scale stochastic systems, and need to be managed using simple local rules that produce coherent behavior at the macroscopic level. The lectures will describe a variety of classical models that can be used to help understand the behavior of large-scale stochastic networks. Queueing and loss networks will be studied, as well as random-access schemes and the concepts of decentralized optimization and distributed control. Parallels will be drawn with models from physics and economics.

 

Primer: Markov chains and stationary measures

 

Topic 1: Loss networks

We discuss the concept of reversibility and how this can be applied to loss networks, a class of multi-dimensional Markov processes that have a product-form solution. Loss networks provide a model for the internet, but also for certain interacting particle systems in physics. We showthat the control of loss networks is related to certain optimization problems.

 

Topic 2: Queueing networks

We discuss queueing networks, in which customers (or jobs or packets) wait for service by one or several servers. First, we show how to model a single queue as a Markov process, and derive information on the distribution of the queue size. We then consider network of queues as multi-dimensional Markov processes and present classes of networks that are amenable to analysis and give rise to product-form solutions.

 

Topic 3: Random access networks

Motivated by wireless networks, we consider a network in which users attempt to share the network capacity while avoiding interference. We begin by supposing users form the vertex set of an interference graph, with an edge between two nodes if they interfere with each other, for instance within a geographical area. Then, we analyze this model as a reversible Markov process and use its closed-form solution to design algorithms for distributed control.

 

Topic 4: Research challenges

We will discuss several open problem related to resource allocation and scheduling in stochastic networks that built on the theory presented in Topics 1-3, but that also requires to go considerably beyond the state-of-the-art.

 

Set up of the Training Week

The training weeks will roughly have the following set-up.

• Preparation. The lecturers prepare material that the participants should study before the training week starts. This material may include assignments  and video lectures about basic concepts in stochastics or algorithmics in general and/or about basic concepts in the topics of the training weeks.
• The training week. The first days of the training week will cover certain standard techniques and results from the area. Later days then focus on a single topic, often at the interface of algorithmics and stochastics; these topics may also provide opportunities for internships.

Programme Training week 2