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
Events
CWIInria Workshop
 20170919T12:30:00+02:00
 20170920T13:00:00+02:00
CWIInria Workshop
Start: 20170919 12:30:00+02:00 End: 20170920 13:00:00+02:00
Everybody is welcome to attend this first workshop of the CWIInria International Lab. You will find more information on the website. For registration please use the event url.
NETWORKS 2017: Scientific Conference
 20170607T09:30:00+02:00
 20170609T17:00:00+02:00
NETWORKS 2017: Scientific Conference
Start: 20170607 09:30:00+02:00 End: 20170609 17:00:00+02:00
On 79 June 2017 NETWORKS organizes the first large conference in the framework of the NETWORKS programme. On 7 and 9 June a scientific conference with 4 parallel tracks, each focussing on a specific aspect of networks. On 8 June a public event is organized. You'll find more information about the program and registration on the website.
N&O Lecture Stefan Weltge (ETH): Polytopes in the 0/1Cube with Bounded ChvátalGomory Rank
 20170222T10:00:00+01:00
 20170222T11:00:00+01:00
N&O Lecture Stefan Weltge (ETH): Polytopes in the 0/1Cube with Bounded ChvátalGomory Rank
Start: 20170222 10:00:00+01:00 End: 20170222 11:00:00+01:00
Everyone who is interested is welcome to attend this CWI public lecture of Stefan.
Abstract: Let P be any polytope contained in [0,1]^n and S be the set of
its integer points. We prove that P has bounded ChvátalGomory rank
(CGrank) provided that S has bounded pitch and bounded gap, where the
pitch is the minimum integer p such that all pdimensional faces of [0,1]^n
have a nonempty intersection with S, and the gap is a measure of the size
of the facet coefficients of conv(S). Let H[S] denote the subgraph of the
ncube induced by the vertices not in S. We prove that if H[S] does not
contain a subdivision of a large complete graph, then both the pitch and
the gap are bounded. By our main result, this implies that the CGrank of
R is bounded as a function of the treewidth of H[S]. This generalizes a
recent theorem of Cornuéjols and Lee (2016), who proved that the CGrank is
always bounded if the treewidth of H[S] is at most 2. This is joint work
with Yohann Benchetrit, Samuel Fiorini and Tony Huynh.
N&O Lecture Pieter Kleer (CWI): Potential Function Minimizers of Combinatorial Congestion Games: Efficiency and Computation
 20170215T10:00:00+01:00
 20170215T11:00:00+01:00
N&O Lecture Pieter Kleer (CWI): Potential Function Minimizers of Combinatorial Congestion Games: Efficiency and Computation
Start: 20170215 10:00:00+01:00 End: 20170215 11:00:00+01:00
Everyone is welcome to attend the public CWI lecture of Pieter Kleer.
Abstract:
Congestion games are an important class of games, introduced by Rosenthal in 1973, which have been studied extensively. Every player has to choose a subset of resources (which is called a strategy), and her payoff depends on the the chosen resources and the number of other players that choose the same resources. Nash equilibria of such games can be characterized by the local minima of Rosenthal's potential function.
In this work, we consider polytopal congestion games in which the strategies of the players are (implicitly) given as the binary vectors of some playerdependent polytope. The sum of these polytopes is called the aggregation polytope. For aggregation polytopes with a boxtotally dual integral (boxTDI) description, and the integer decomposition property (IDP), we give (i) a unifying approach for computing Nash equilibria in (strongly) polynomial time, and (ii) derive tight inefficiency bounds for these equilibria. Examples of polytopal congestion games which satisfy IDP and boxTDI are symmetric totally unimodular congestion games, nonsymmetric matroid congestion games, symmetric rarborescence congestion games, and common source network congestion games. In general, our results also reveal that the combination of IDP and boxTDI gives rise to an efficient approach to compute a pure Nash equilibrium whose inefficiency is much better than in general congestion games.
Joint work with Guido Schaefer
N&O Lecture Jesper Nederlof (TU/e): Faster Space Efficient Algorithms for Subset Sum and Knapsack
 20170208T10:00:00+01:00
 20170208T11:00:00+01:00
N&O Lecture Jesper Nederlof (TU/e): Faster Space Efficient Algorithms for Subset Sum and Knapsack
Start: 20170208 10:00:00+01:00 End: 20170208 11:00:00+01:00
Everyone is welcome to attend the public lecture of Jesper Nederlof. Abstract:
Faster Space Efficient Algorithms for Subset Sum and Knapsack
We present a randomized Monte Carlo algorithm that solves a given instance of Subset Sum on n integers using O*(2^{0.86n}) time and O*(1) space, where O*() suppresses factors polynomial in the input size. The algorithm assumes random access to the random bits used. The same result can be obtained for Knapsack on n items, and the same methods also have consequences for the kSum problem. Joint work with Nikhil Bansal, Shashwat Garg and Nikhil Vyas.
N&O Lecture Ross Kang (Radboud University): Colouring powers of graphs with one cycle length forbidden
 20170201T10:00:00+01:00
 20170201T11:00:00+01:00
N&O Lecture Ross Kang (Radboud University): Colouring powers of graphs with one cycle length forbidden
Start: 20170201 10:00:00+01:00 End: 20170201 11:00:00+01:00
Everyone is welcome to attend the N&O lecture of Ross Kang at CWI.
Abstract: Graph powers arise naturally in the study of, for example, efficient
network communication. Some basic problems have long been studied and
remain stubbornly open. I will first discuss previous work on the
chromatic number of graph powers, for graphs of maximum degree d,
often taking d very large. This is related to conjectures of Bollobás
and of Erdos and Nešetril from the 1980s. Then I will discuss
restricted versions where we impose an additional girth or cycle
length restriction. This relates to a problem of Alon and Mohar. This
is joint work with Francois Pirot.
Members of Networks and Optimization
Publications

Hu, H, & Laurent, M. (2017). On the linear extension complexity of stable set polytopes for perfect graphs.

Laurent, M. (2017, June). Review of "Jean Bernard Lasserre: An introduction to polynomial and semialgebraic optimization". Nieuw Archief voor Wiskunde.

Kleer, P.S, & Schäfer, G. (2017). Tight inefficiency bounds for perceptionparameterized affine congestion games. In Algorithms and Complexity (pp. 381–392). doi:10.1007/9783319575865_32

Laurent, M, Seminaroti, M, & Tanigawa, S.I. (2017). A structural characterization for certifying Robinsonian matrices. Electronic Journal of Combinatorics, 24(2).

van Apeldoorn, J, Gilyén, A.P, Gribling, S.J, & de Wolf, R. M. (2017). Quantum SDPsolvers. In FOCS.

de Klerk, E, Hess, R, & Laurent, M. (2017). Improved convergence rates for Lasserretype hierarchies of upper bounds for boxconstrained polynomial optimization. SIAM Journal on Optimization, 27(1), 347–367. doi:10.1137/16M1065264

Laurent, M, & Seminaroti, M. (2017). A LexBFSbased recognition algorithm for Robinsonian matrices. Discrete Applied Mathematics, 222, 151–165. doi:10.1016/j.dam.2017.01.027

Geelen, J, Gerards, A.M.H, & Whittle, G. (2017). QuasiGraphic Matroids. Journal of Graph Theory. doi:10.1002/jgt.22143

Bansal, N, Dadush, D.N, & Garg, S. (2016). An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound. In Proceedings  Annual IEEE Symposium on Foundations of Computer Science, FOCS (pp. 788–799). doi:10.1109/FOCS.2016.89

de Laat, D. (2016). Moment methods in energy minimization: New bounds for Riesz minimal energy problems.
Current Projects

New Frontiers in Lattice Algorithms and Design

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

Stanford University

Radboud Universiteit

Technische Universiteit Eindhoven

Universiteit Leiden

Universiteit van Amsterdam

Universiteit van Amsterdam