Description

CWI-Inria Workshop

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.

• Web
• Email: susanne@cwi.nl
• Phone: 020-592 4189
• iCal

NETWORKS 2017: Scientific Conference

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.

• Web
• Email: Marieke Kranenburg
• Phone: +31 020 - 525 6499
• iCal

N&O Lecture Stefan Weltge (ETH): Polytopes in the 0/1-Cube with Bounded Chvátal-Gomory Rank

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.

• Web
• iCal

N&O Lecture Pieter Kleer (CWI): Potential Function Minimizers of Combinatorial Congestion Games: Efficiency and Computation

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

• Web
• iCal

N&O Lecture Jesper Nederlof (TU/e): Faster Space Efficient Algorithms for Subset Sum and Knapsack

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.

• Web
• iCal

N&O Lecture Ross Kang (Radboud University): Colouring powers of graphs with one cycle length forbidden

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.

• Web
• iCal