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

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 in the research project "Approximation Algorithms, Quantum Information and Semidefinite Optimization" - Read More…

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.

Postdoc on the subject of Network Games with Combinatorial Structures - Read More…

News

Events

CWI-Inria Workshop

  • 2017-09-19T12:30:00+02:00
  • 2017-09-20T13:00:00+02:00
September 19 Tuesday

Start: 2017-09-19 12:30:00+02:00 End: 2017-09-20 13:00:00+02:00

CWI Congress Centre

Everybody is welcome to attend this first workshop of the CWI-Inria International Lab. You will find more information on the website. For registration please use the event url.

NETWORKS 2017: Scientific Conference

  • 2017-06-07T09:30:00+02:00
  • 2017-06-09T17:00:00+02:00
June 7 Wednesday

Start: 2017-06-07 09:30:00+02:00 End: 2017-06-09 17:00:00+02:00

Congress Centre Amsterdam Science Park

On 7-9 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/1-Cube with Bounded Chvátal-Gomory Rank

  • 2017-02-22T10:00:00+01:00
  • 2017-02-22T11:00:00+01:00
February 22 Wednesday

Start: 2017-02-22 10:00:00+01:00 End: 2017-02-22 11:00:00+01:00

Room L017, CWI, Science Park 123, Amsterdam

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átal-Gomory rank
(CG-rank) provided that S has bounded pitch and bounded gap, where the
pitch is the minimum integer p such that all p-dimensional 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
n-cube 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 CG-rank 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 CG-rank 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

  • 2017-02-15T10:00:00+01:00
  • 2017-02-15T11:00:00+01:00
February 15 Wednesday

Start: 2017-02-15 10:00:00+01:00 End: 2017-02-15 11:00:00+01:00

CWI room L016

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 pay-off 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 player-dependent polytope. The sum of these polytopes is called the aggregation polytope. For aggregation polytopes with a box-totally dual integral (box-TDI) 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 box-TDI are symmetric totally unimodular congestion games, non-symmetric matroid congestion games, symmetric r-arborescence congestion games, and common source network congestion games. In general, our results also reveal that the combination of IDP and box-TDI 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

  • 2017-02-08T10:00:00+01:00
  • 2017-02-08T11:00:00+01:00
February 8 Wednesday

Start: 2017-02-08 10:00:00+01:00 End: 2017-02-08 11:00:00+01:00

Room L016 - CWI

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 k-Sum 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

  • 2017-02-01T10:00:00+01:00
  • 2017-02-01T11:00:00+01:00
February 1 Wednesday

Start: 2017-02-01 10:00:00+01:00 End: 2017-02-01 11:00:00+01:00

Room L016, ground floor CWI

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

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
  • 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
  • Stanford University
  • Radboud Universiteit
  • Technische Universiteit Eindhoven
  • Universiteit Leiden
  • Universiteit van Amsterdam
  • Universiteit van Amsterdam