Description
Leader of the group Networks and Optimization: Guido Schäfer.
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.
Vacancies
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 peerreviewed journals of the field, culminating in a PhD thesis to be defended in public.
News
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)
 20161202T09:00:00+01:00
 20161202T11:30:00+01:00
PhD Defence Matteo Seminaroti (N&O)
Start: 20161202 09:00:00+01:00 End: 20161202 11:30:00+01:00
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 TreeLikeness
 20161130T10:00:00+01:00
 20161130T11:00:00+01:00
N&O Lecture Matthias Mnich: New Algorithms for Maximum Disjoint Paths Based on TreeLikeness
Start: 20161130 10:00:00+01:00 End: 20161130 11:00:00+01:00
We would like to announce the following lecture from Matthias Mnich (Bonn) at the N&O seminar:
Abstract:
We study the classical NPhard problems of finding maximumsize subsets
from given sets of k terminal pairs that can be routed via edgedisjoint
paths (MaxEDP) or nodedisjoint 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)
 20161027T08:00:00+02:00
 20161027T11:00:00+02:00
PhD Defence Teresa Piovesan (N&O/A&C)
Start: 20161027 08:00:00+02:00 End: 20161027 11:00:00+02:00
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)
 20160628T09:00:00+02:00
 20160628T10:00:00+02:00
N&O lecture: Frank Permenter (MIT)
Start: 20160628 09:00:00+02:00 End: 20160628 10:00:00+02:00
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 primaldual pair over a lowerdimensional symmetric conenamely, the coneofsquares 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 *algebrabased 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
 20160617T13:00:00+02:00
 20160617T14:00:00+02:00
N&O Lecture: Joe Halpern, Cornell University
Start: 20160617 13:00:00+02:00 End: 20160617 14:00:00+02:00
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 resourcebounded agents.
Abstract:
There have been two major lines of research aimed at capturing
resourcebounded 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 wellknown phenomena like firstimpressionmatters
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)
 20160614T12:00:00+02:00
 20160614T13:00:00+02:00
N&O Lecture: Bodo Manthey (University of Twente)
Start: 20160614 12:00:00+02:00 End: 20160614 13:00:00+02:00
Everyone is invited to attend the CWI Lecture from Bodo Manthey with the title: Smoothed Analysis of the 2Opt Heuristic for the TSP
Abstract:
The 2opt 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 worstcase runningtime and
approximation ratio are poor.
In order to explain the practical performance of 2opt, 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 runningtime
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.)
Members of Networks and Optimization
Publications

Laurent, M, & Tanigawa, S.I. (2017). Perfect elimination orderings for symmetric matrices.

de Klerk, E, Lasserre, J.B, Laurent, M, & Sun, Z. (2017). Boundconstrained polynomial optimization using only elementary calculations. Mathematics of Operations Research.

de Klerk, E, & Laurent, M. (2017). Comparison of Lasserre's measurebased bounds for polynomial optimization to bounds obtained by simulated annealing.

de Klerk, E, Laurent, M, Sun, Z, & Vera, J.C. (2017). On the convergence rate of grid search for polynomial optimization over the simplex. Optimization Letters, 11(3), 597–608. doi:10.1007/s1159001610237

de Klerk, E, Laurent, M, & Sun, Z. (2017). Convergence analysis for Lasserre’s measurebased hierarchy of upper bounds for polynomial optimization. Mathematical Programming, 162(1), 363–392. doi:10.1007/s1010701610431

Gribling, S.J, de Laat, D, & Laurent, M. (2017). Matrices with high completely positive semidefinite rank. Linear Algebra and Its Applications, 513, 122–148. doi:10.1016/j.laa.2016.10.015

Burgdorf, S, Laurent, M, & Piovesan, T. (2017). On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings. Electronic Journal of Linear Algebra, 32, 15–40. doi:10.13001/10813810.3201

Dadush, D.N, & Regev, O. (2016). Towards Strong Reverse MinkowskiType Inequalities for Lattices. In Proceedings  Annual IEEE Symposium on Foundations of Computer Science, FOCS (pp. 447–456). doi:10.1109/FOCS.2016.55

Seminaroti, M. (2016, December 2). Combinatorial algorithms for the seriation problem.

Apt, K.R, de Keijzer, B, Rahn, M.M, Schäfer, G, & Simon, S.E. (2016). Coordination games on graphs. International Journal of Game Theory. doi:10.1007/s0018201605608
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

AQSOApproximation Algorithms, Quantum Information and Semidefinite Optimization

CoMGACombining Machine Learning and Gametheoretic Approaches for Cluster Analysis

ITSLOGReal Time Verkeersdata voor Goederenvervoer (ITSLOG)

NetworksNetworks (eerste fase)

SocialACTSocietal Impact Games
Partners

CTVrede

Rovecom BV

Stanford University

Radboud Universiteit

Technische Universiteit Eindhoven

Universiteit Leiden

Universiteit van Amsterdam

Universiteit van Amsterdam