# Description

### Leader of the group Networks and Optimization: Guido Schäfer.

In today’s society, complex systems surround us. From transport and traffic, to behavioural economics and operations management, real-world applications often demand that we identify simple, optimal solutions among a huge set of possibilities. Our research group Networks and Optimization works to make this complexity manageable.

By combining techniques from mathematics and computer science, we develop algorithmic methods to tackle complex optimization problems. Our research provides efficient solutions to some of the world’s most challenging problems, for example in planning, scheduling and routing.

More

## Postdoc in the research project "Approximation Algorithms, Quantum Information and Semidefinite Optimization"

The research project “Approximation algorithms, quantum information and semidefinite optimization” aims to explore the limits of efficient computation within classical and quantum computing, using semidefinite optimization as a main unifying tool. The position involves research into the mathematical and computer science aspects of approximation algorithms for discrete optimization, quantum entanglement in communication, and complexity of fundamental problems in classical and quantum computing. More information about the project can be found at this website.

## Postdoc on the subject of Network Games with Combinatorial Structures

The goal of this project is to study the computation and inefficiency of equilibria in strategic games on networks. One key aspect is to identify combinatorial structures that allow for the efficient computation of equilibria with provable inefficiency guarantees. Another key aspect is to investigate the potential of exploiting combinatorial structures to develop coordination mechanisms that reduce the inefficiency caused by selfish behavior.

## PhD Student on the subject of High Dimensional Geometric Algorithms

The student will conduct research on the subject of High Dimensional Geometric Algorithms, present the fruits of this research at top conferences and publish them in quality peer-reviewed journals of the field, culminating in a PhD thesis to be defended in public.

## Monique Laurent elected as Fellow of SIAM

CWI researcher Monique Laurent is elected as a Fellow of the international Society for Industrial and Applied Mathematics – SIAM. This prestigious Fellowship honours SIAM members who have made outstanding contributions to these fields. Laurent, who is a member of the management team of CWI and a professor at Tilburg University, receives the fellowship for her contributions to discrete and polynomial optimization and revealing interactions between them.

## Rubicon grants for David de Laat and Alessandro Zocca

CWI researchers David de Laat and Alessandro Zocca both received an NWO Rubicon grant. De Laat will study new techniques to compute optimal packings at MIT for one year, and Zocca will study renewables and uncertainty in future power systems at Caltech for two years. NWO granted these subsidies to 22 young, highly promising research talents to gain international research experience at foreign top institutes.

## Better ranking for big data using seriation solution

The recent availability of large data sets leads to the challenge of identifying patterns and structures in them. These patterns can be deployed to improve the user experience

## Quantum entanglement can make communications more efficient

Entanglement – a quantum mechanical correlation between particles that can exist even over long distances – might be used for future ways of communication.

## Events

### PhD Defence Matteo Seminaroti (N&O)

• 2016-12-02T09:00:00+01:00
• 2016-12-02T11:30:00+01:00
December 2 Friday

## PhD Defence Matteo Seminaroti (N&O)

Start: 2016-12-02 09:00:00+01:00 End: 2016-12-02 11:30:00+01:00

De Aula van Universiteit Tilburg

Everyone is invited to attend the defence of Matteo Seminaroti of his thesis
"Combinatorial Algorithms for the Seriation Problem"

Promotor: Prof.dr. Monique Laurent. Copromotor: Prof.dir.ir. Renata Sotirov

### N&O Lecture Matthias Mnich: New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness

• 2016-11-30T10:00:00+01:00
• 2016-11-30T11:00:00+01:00
November 30 Wednesday

## N&O Lecture Matthias Mnich: New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness

Start: 2016-11-30 10:00:00+01:00 End: 2016-11-30 11:00:00+01:00

Room L120, first floor CWI, Science Park 123 Amsterdam

We would like to announce the following lecture from Matthias Mnich (Bonn) at the N&O seminar:

Abstract:

We study the classical NP-hard problems of finding maximum-size subsets
from given sets of k terminal pairs that can be routed via edge-disjoint
paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph. The
approximability of MaxEDP/MaxNDP is currently not well understood; the
best known lower bound is \Omega(log^{1/2−ε}n), assuming NP
\not\subseteq ZPTIME(n^{polylog(n)}). This constitutes a significant gap
to the best known approximation upper bound of O(\sqrt(n)) due to
Chekuri et al. (2006), and closing this gap is currently one of the big
open problems in approximation algorithms. In their seminal paper,
Raghavan and Thompson (Combinatorica, 1987) introduce the technique of
randomized rounding for LPs; their technique gives an O(1)-approximation
when edges (or nodes) may be used by O(log(n)/loglog(n)) paths.

We strengthen these fundamental results. We provide new bounds
formulated in terms of the feedback vertex set number r of a graph,
which measures its vertex deletion distance to a forest. In particular,
we obtain
the following results:
– For MaxEDP, we give an O(\sqrt(r) * log(kr))-approximation algorithm.
Up to a logarithmic factor, our result strengthens the best known ratio
O(\sqrt(n)) due to Chekuri et al., as r \leq n.
– Further, we show how to route \Omega(OPT * ) pairs with congestion
bounded by O(logkr/loglogkr), strengthening the bound obtained by the
classic approach of Raghavan and Thompson.

(Joint work with Joachim Spoerhase and Krzysztof Fleszar).

### PhD Defence Teresa Piovesan (N&O/A&C)

• 2016-10-27T08:00:00+02:00
• 2016-10-27T11:00:00+02:00
October 27 Thursday

## PhD Defence Teresa Piovesan (N&O/A&C)

Start: 2016-10-27 08:00:00+02:00 End: 2016-10-27 11:00:00+02:00

Agnietenkapel, Oudezijds Voorburgwal 231, Amsterdam

Everyone is welcome to attend the public defence of Teresa Piovesan, of her thesis "Quantum entanglement: insights via graph parameters and conic optimization"

Promotors:  Prof.dr. Harry Buhrman and Prof.dr. Monique Laurent

More information: see the news item 'Quantum entanglement can make some communications more efficient'.

### N&O lecture: Frank Permenter (MIT)

• 2016-06-28T09:00:00+02:00
• 2016-06-28T10:00:00+02:00
June 28 Tuesday

## N&O lecture: Frank Permenter (MIT)

Start: 2016-06-28 09:00:00+02:00 End: 2016-06-28 10:00:00+02:00

Room L016, ground floor CWI

Everyone is very welcome to attend the CWI lecture of Frank Permenter (MIT) with the title: Dimension Reduction For SDPs Via Jordan Algebras.

Abstract:
We propose a new method for simplifying semidefinite programs inspired by symmetry reduction. Specifically, we show if a projection satisfies certain invariance conditions, restricting to its range yields an equivalent primal-dual pair over a lower-dimensional symmetric cone-namely, the cone-of-squares of a Jordan subalgebra of symmetric matrices.  We then give a simple algorithm for minimizing the rank of this projection and hence the dimension of this cone. Finally, we explore connections with *-algebra-based reduction methods, which, along with symmetry reduction, can be seen as special cases of our method. Joint work with Pablo Parrilo.

### N&O Lecture: Joe Halpern, Cornell University

• 2016-06-17T13:00:00+02:00
• 2016-06-17T14:00:00+02:00
June 17 Friday

## N&O Lecture: Joe Halpern, Cornell University

Start: 2016-06-17 13:00:00+02:00 End: 2016-06-17 14:00:00+02:00

Room L016, ground floor CWI

Everyone who is interested is welcome to attend the CWI Lecture of Joe Halpern, Cornell University.   The title of his lecture is:  Decision theory with resource-bounded agents.

Abstract:
There have been two major lines of research aimed at capturing
resource-bounded players in game theory.  The first, initiated by Rubinstein,
charges an agent for doing costly computation; the second, initiated by Neyman
does not charge for computation, but limits the computation that agents
can do, typically by modeling agents as finite automata.  We review recent
work on applying both approaches in the context of decision theory.
For the first approach, we take the objects of choice in a decision
problem to be Turing machines, and charge players for the complexity'' of
the Turing machine chosen (e.g., its running time).  This approach can be
used to explain well-known phenomena like first-impression-matters
biases (i.e., people tend to put more weight on evidence they hear early on)
and belief polarization (two people with different prior beliefs,
hearing the same evidence, can end up with diametrically opposed
conclusions) as the outcomes of quite rational decisions.
For the second approach, we model people as finite automata, and provide a
simple algorithm that, on a problem that captures a number of settings of
interest, provably performs optimally as the number of states in
the automaton increases.  Perhaps more importantly, it seems to capture a
number of features of human behavior, as observed in experiments.

This is joint work with Rafael Pass and Lior Seeman.
No previous background is assumed.

### N&O Lecture: Bodo Manthey (University of Twente)

• 2016-06-14T12:00:00+02:00
• 2016-06-14T13:00:00+02:00
June 14 Tuesday

## N&O Lecture: Bodo Manthey (University of Twente)

Start: 2016-06-14 12:00:00+02:00 End: 2016-06-14 13:00:00+02:00

Room L016, ground floor CWI

Everyone is invited to attend the CWI Lecture from Bodo Manthey with the title: Smoothed Analysis of the 2-Opt Heuristic for the TSP

Abstract:

The 2-opt heuristic is a very simple local search heuristic for the
traveling salesman problem. While it usually converges quickly in
practice to a good solution, its worst-case running-time and
approximation ratio are poor.

In order to explain the practical performance of 2-opt, we use smoothed
analysis: an adversary places n points arbitrarily, and then the points
are perturbed by adding independent Gaussian random variables of
standard deviation sigma. We show that the maximum expected running-time
that the adversary can achieve is bounded by a polynomial in n and
1/sigma and that the maximum expected approximation ratio is
O(log(1/sigma)).

(Joint work with Rianne Veenstra and Marvin Künnemann.)

## Current Projects

• New Frontiers in Lattice Algorithms and Design
• Optimalisatie van planningsvraagstukken in de touringcarsector
• Verbeteren van de efficiency en prestatie van logistieke processen in de binnevaart
• Wiskundecluster DIAMANT / Tenure Track positie Daniel Dadush
• AQSO
Approximation Algorithms, Quantum Information and Semidefinite Optimization
• CoMGA
Combining Machine Learning and Game-theoretic Approaches for Cluster Analysis
• ITSLOG
Real Time Verkeersdata voor Goederenvervoer (ITSLOG)
• Networks
Networks (eerste fase)
• SocialACT
Societal Impact Games

## Partners

• CTVrede
• Rovecom BV
• Stanford University