Events

 
Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09 
(Meeting ID: 849 0964 5595, Passcode: 772448)

Speaker: Steven Miltenburg (VU)

Title: Complexity of fixed order routing

Abstract:

We consider the classic Vehicle Routing Problem with the additional property that all requests are ordered and the subtour of each server (or vehicle) must obey the fixed order. A scheduling version of this problem was introduced by Bosman et al. (2019). We study several metric spaces and objective functions and our results show that in some settings such a fixed order simplifies the problem, while in others it makes an easy problem become NP-hard. For general metrics, we show that c-capacitated VRP remains APX-hard in the fixed order setting for c = 3 and show that the well-known iterated tour partitioning algorithm yields a (2 − 1/c)-approximation. When all points are on the line, we show that the fixed order restriction makes VRP NP-hard to solve for minimizing total completion time or maximum completion time, in contrast to standard VRP.

The talk is based on joint work with René Sitters and Tim Oosterwijk.

Video:

Slides:

Speaker: Antonina Khramova (TU/e)

Title: A linear programming bound for sum-rank-metric codes

Abstract:

The sum-rank metric is a generalization of the well-known Hamming and rank metrics, where we consider tuples of matrices (possibly of different sizes) over a finite field, and the distance between two tuples is the sum of ranks of differences of respective entries of the tuple.

In this talk we use Delsarte's LP method to derive a linear programming bound on the maximum cardinality of error-correcting codes in the sum-rank metric. The Delsarte's LP bound has been previously obtained for Hamming metric, rank metric, Lee metric, and others, but the sum-rank-metric case remained open. To derive the new LP bound, we propose a way to construct an association scheme for the sum-rank metric, since the approach used in the Hamming and the rank-metric cases fails due to the associated graph not being distance-regular in general.

Based on computational experiments on relatively small instances, we observe that the obtained bound outperforms all bounds previously known for sum-rank-metric codes.

The talk is based on joint work with Aida Abiad, Alexander L. Gavrilyuk, and Ilia Ponomarenko. The paper is available at: https://arxiv.org/abs/2406.15926


Video:

Slides:

 
Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09 
(Meeting ID: 849 0964 5595, Passcode: 772448)

Speaker: Nando Leijenhorst (TU Delft) 

Title: Optimality and uniqueness of the D4 root system

Abstract:

The spherical code problem asks how to arrange N points on the unit sphere in dimension n such that the distance between the closest pair of points is maximized.

We prove that for 24 points in dimension 4, the D4 root system is the optimal configuration, by showing that it is the unique solution for the kissing number problem in dimension 4, up to isometry. For this we use a semidefinite programming relaxation of the second step of the Lasserre hierarchy for spherical codes, for which we obtain an exact optimal solution by rounding the numerical solution using the techniques of [Cohn, de Laat, Leijenhorst, 2024+].

In this talk, I will explain the steps needed to prove the result, including the main steps of the rounding procedure.

Joint work with David de Laat and Willem de Muinck Keizer (https://arxiv.org/abs/2404.18794).
The rounding procedure is joint work with Henry Cohn and David de Laat (https://arxiv.org/abs/2403.16874).

Video:

Slides:
Slides

Speaker: Artem Tsikiridis (CWI) 

Title: Pandora's Box Problem Over Time

Abstract:

The Pandora's Box problem models the search for the best alternative when evaluation is costly. In its simplest variant, a decision maker is presented with n boxes, each associated with a cost of inspection and a distribution over the reward hidden within. The decision maker inspects a subset of these boxes one after the other, in a possibly adaptive ordering, and obtains as utility the difference between the largest reward uncovered and the sum of the inspection costs. While this classic version of the problem is well understood (Weitzman 1979), recent years have seen a flourishing of the literature on variants of the problem. In this paper, we introduce a general framework -- the Pandora's Box Over Time problem -- that captures a wide range of variants where time plays a role, e.g., as it might constrain the schedules of exploration and influence both costs and rewards. In the Pandora's Box Over Time problem, each box is characterized by time-dependent rewards and costs, and inspecting it might require a box-specific processing time. Moreover, once a box is inspected, its reward may deteriorate over time, possibly differently for each box. Our main result is an efficient 21.3-approximation to the optimal strategy, which is NP-hard to compute in general. We further obtain improved results for the natural special cases where boxes have no processing time, or when costs and reward distributions do not depend on time (but rewards may deteriorate after inspecting).  

Joint work with Georgios Amanatidis, Federico Fusco and Rebecca Reiffenhäuser (https://arxiv.org/abs/2407.15261).  

Video:

Slides:
Slides

Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09 
(Meeting ID: 849 0964 5595, Passcode: 772448)

Speaker: Neil Olver (LSE)

Title: Structure and stability of equilibria in a queue-based traffic model

Abstract:
We consider the Vickrey bottleneck model of traffic flow in a network. Users control infinitesimal flow particles aiming to travel from a
source to a destination as quickly as possible. Flow patterns vary over time, and congestion effects are modelled through (deterministic) queues, which form whenever the inflow into a link exceeds its capacity. Our goal is a better understanding of equilibrium behaviour in this model, where each user selects a quickest possible route taking queueing delays into account.

I will introduce the model, discuss our current understanding of the structure of equilibria, and describe recent work showing that the model exhibits strong stability properties. In particular, if users control "packets" of non-negligible size, or if users may choose slightly suboptimal routes, we demonstrate that a resulting equilibrium remains close to the equilibrium of the original model.

Video:

Slides:
Slides

Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09 
(Meeting ID: 849 0964 5595, Passcode: 772448)

Speaker: Aida Khajavirad (Lehigh University)

Title: The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization

Abstract:
With the goal of obtaining strong relaxations for binary polynomial optimization problems, we introduce the pseudo-Boolean polytope. By representing the pseudo-Boolean polytope via a signed hypergraph, we obtain sufficient conditions under which this polytope has a polynomial-size extended formulation. Our new framework unifies and extends all prior results on the existence of polynomial-size extended formulations for the convex hull of the feasible region of binary polynomial optimization problems of degree at least three. This is joint work with Alberto Del Pia.

Video:

Slides:
Slides

Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09 
(Meeting ID: 849 0964 5595, Passcode: 772448)

Speaker: Caroline Jagtenberg (VU Amsterdam)

Title: Analytics for community first response

Abstract:
In Community First Responder systems, traditional ambulance response is augmented by a network of trained volunteers who are dispatched via an app. A central application of such systems is cardiac arrest, where shortening the time to CPR is crucial. A number of such community first responder (CFR) systems are active worldwide, for example HartslagNu in the Netherlands and GoodSAM in the UK, Australia and New Zealand. We have received detailed data from the latter, which we combine with mathematical modeling to optimize the following:

1) Recruitment. For a target performance level, how many volunteers are needed and from which locations should they be recruited? We model the presence of volunteers throughout a region as a Poisson point process, which permits the computation of the response-time distribution of the first-arriving volunteer. Combining this with known survival-rate functions, we deduce survival probabilities in the cardiac arrest setting. We then use convex optimization to compute an optimal location distribution of volunteers across the region.

2) Phased alerts. GoodSAM notifies volunteers in batches with built-in time delays. The policy that defines the batch sizes and delays affects the time to CPR as well as the number of redundant volunteer arrivals. We start by estimating these KPIs for various policies through Monte Carlo Simulation. We continue by using machine learning to predict the best policy to use, given where the volunteers are observed in relation to the patient. We do this by formulating the problem as a multiclass classification problem, for which we train a tree on the results from the simulations above. We compare the performance of the tree against a policy designed by dynamic programming. Finally, we look into optimal decision trees which go beyond the heuristic nature of machine learning algorithms.

Slides:
Slides

 
Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09 
(Meeting ID: 849 0964 5595, Passcode: 772448)

Speaker: Alireza Yazdani (TU Eindhoven) 

Title: A Clustering-based Uncertainty Set for Robust Optimization

Abstract:

In this paper, we introduce a new approach for constructing data-driven uncertainty sets in robust optimization through volume-based clustering, which we termed minimum volume norm-based clustering. This clustering approach provides greater flexibility in capturing diverse data patterns and extends the concept of minimum volume ellipsoid clustering by incorporating norm-based shapes for subregions alongside ellipsoids. We present a mixed-integer conic optimization model for minimum volume norm-based clustering, enabling customizable cluster shapes based on any vector norm in $\mathbb{R}^d$. The model we propose has the ability to detect outliers and identify overlapped clusters. Due to the computational complexity of the model, we develop an efficient iterative approximation algorithm to find near-optimal minimum-volume clusters. We compare the performance of the developed algorithm with commonly used clustering methods in the literature, such as K-means and Gaussian mixtures model clustering, to show the algorithm's efficiency in clustering data. Additionally, we conduct experiments to demonstrate the effectiveness of our approach in generating uncertainty sets. We compare the results of our method's generated uncertainty set with those from the literature. We compare the performance of the solutions generated from our method's constructed uncertainty set with others from the literature. By conducting these experiments, we demonstrate that our proposed method leads to less conservative solutions in robust optimization problems.

Video:

Speaker: Jesse van Rhijn (University of Twente)

Title: Complexity of Local Search for Euclidean Clustering Problems

Abstract:

In Euclidean clustering problems, one is given a set of d-dimensional points, and is asked to partition the set into clusters such that the points within a cluster are close by some measure. A natural measure is the squared Euclidean distance between two objects, used in the well-studied k-Means clustering problem. For this problem, local search algorithms are among the most popular methods for practical use. We show that the simplest local search method for k-Means clustering, the Hartigan-Wong method, is PLS-complete, even for k = 2. This shows that finding locally optimal clusterings under this method is as hard as for any local search problem. The same methods we use in our proofs can be easily adapted to yield PLS-completeness for Squared Euclidean Max Cut under the Flip neighborhood, which is equivalent to Min Sum 2-Clustering.

Paper available at https://arxiv.org/abs/2312.14916

Video:

Slides:
Slides

Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09 
(Meeting ID: 849 0964 5595, Passcode: 772448)

Speaker: Sami Davies (Simons Institute & UC Berkeley)

Title: Combinatorial LP-norm Correlation Clustering

Abstract:
Correlation clustering is a natural model arising from community detection problems. A complete graph is given with each edge labeled as either positive or negative; two vertices are connected by a positive edge when they are “similar" and want to be clustered together, while a negative edge indicates vertices that are “dissimilar" and want to be in different clusters. The goal is to find a clustering that minimizes an objective capturing the edges’ disagreements with respect to the clustering. In this talk, we focus on objectives that minimize the $\ell_p$-norm of the disagreement vector, which is a well-studied class of objective. Our work provides the first purely combinatorial constant factor approximation algorithms for these problems. Additionally, we provide an algorithm that produces a single clustering solution that is *simultaneously* constant approximate for all $\ell_p$-norms of the disagreement vector. This proves that minimal sacrifice is needed in order to optimize different local norms. The combinatorial nature of our techniques lend to significant run-time improvements, with empirical results showing that our algorithms scale to larger networks that were effectively intractable for previous algorithms.

Video:

Slides:

Slides

Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Speaker: Frank Vallentin (University of Cologne)

Title: Extremal lattice problems (not in the bible)

Abstract:
Lattices (discrete subgroups of n-dimensional Euclidean spaces) are ubiquitous objects in mathematics.

Typical classes of extremal lattice problems are finding good lattices with respect to some parameter, for instance minimizing packing density, maximizing covering density, or minimizing the quantization constant. The "bible" on these extremal lattice problems is the book "Sphere packings, lattices, and groups" [SPLAG] by Conway and Sloane. The first edition appeared in 1988. In the third edition from 1998 and one finds on p. xv the following quote "like the bible, [SPLAG] contains no proofs. This is of course only half true."

Science and technology advances and there is need for lattices which are good for other parameters or properties not yet treated in the bible, like minimizing potential energy, max-min polarization, minimizing Euclidean distortion, coloring the Voronoi cells, or polynomial time decodability.

In this talk I will introduce some of these extremal lattice problems, explain (combinatorial) techniques to attack them, and review open problems.

Video:

Slides:
Slides

Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09 
(Meeting ID: 849 0964 5595, Passcode: 772448)

Speaker: Hilde Verbeek (CWI)

Title: Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast

Abstract:
Sparse suffix sorting is the problem of sorting $b=o(n)$ suffixes of a string of length $n$. Efficient sparse suffix sorting algorithms have existed for more than a decade. Despite the multitude of works and their justified claims for applications in text indexing, the existing algorithms have not been employed by practitioners. Arguably this is because there are no simple, direct, and efficient algorithms for sparse suffix array construction. We provide two new algorithms for constructing the sparse suffix and LCP arrays that are simultaneously simple, direct, small, and fast. In particular, our algorithms are: simple in the sense that they can be implemented using only basic data structures; direct in the sense that the output arrays are not a byproduct of constructing the sparse suffix tree or an LCE data structure; fast in the sense that they run in $O(n \log b)$ time, in the worst case, or in $O(n)$ time, when the total number of suffixes with an LCP value greater than $2^{\lfloor \log \frac{n}{b} \rfloor + 1} − 1$ is in $O(b / \log b)$, matching the time of the optimal yet much more complicated algorithms [Gawrychowski and Kociumaka, SODA 2017; Birenzwige et al., SODA 2020]; and small in the sense that they can be implemented using only $8b + o(b)$ machine words. Our algorithms are simplified, yet non-trivial, space-efficient adaptations of the Monte Carlo algorithm by I et al. for constructing the sparse suffix tree in $O(n \log b)$ time [STACS 2014]. We also provide proof-of-concept experiments to justify our claims on simplicity and efficiency.

Based on https://arxiv.org/abs/2310.09023.

Video:

Slides:
Slides

Speaker: Bram Bekker (TU Delft)

Title: SDP hierarchies for distance-avoiding sets on compact spaces

Abstract:
Witsenhausen's problem asks for the maximum fraction α_n of the n-dimensional unit sphere that can be covered by a measurable set containing no pairs of orthogonal points. We extended well known optimization hierarchies based on the Lovász theta number, like the Lasserre hierarchy, to Witsenhausen's problem and similar problems. These hierarchies are shown to converge and are used to compute the best upper bounds known for αn in low dimensions.

Based on https://arxiv.org/abs/2304.05429.

Video:

Slides:
Slides

Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Speaker: Stefanie Jegelka (MIT)

Title: Machine Learning for discrete optimization: Graph Neural Networks, generalization under shifts, and loss functions

Abstract:
Graph Neural Networks (GNNs) have become a popular tool for learning algorithmic tasks, in particular related to combinatorial optimization. In this talk, we will focus on the “algorithmic reasoning” task of learning a full algorithm. Instead of competing on empirical benchmarks, we will aim to get a better understanding of the model's behavior and generalization properties, i.e., the performance on hold-out data, which is an important question in learning-supported optimization too.
We will try to understand in particular out-of-distribution generalization in widely used message passing GNNs, with an eye on applications in learning for optimization: what may be an appropriate metric for measuring shift in the data? Under what conditions will a GNN generalize to larger graphs?
In the last part of the talk, we will take a brief look at objective (loss) functions for learning with discrete objects, beyond GNNs. 

This talk is based on joint work with Ching-Yao Chuang, Keyulu Xu, Joshua Robinson, Nikos Karalias, Jingling Li, Mozhi Zhang, Simon S. Du, Kenichi Kawarabayashi and Andreas Loukas.

Video:

 
Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09 
(Meeting ID: 849 0964 5595, Passcode: 772448)

Speaker: Pedro Zattoni Scroccaro (TU Delft) 

Title: Learning Drivers’ Preferences: an Inverse Optimization Approach

Abstract:
In Inverse Optimization problems, a learning agent aims to learn how to mimic the behavior of an expert agent, which given an exogenous signal, returns an action. The underlying assumption is that in order to compute its action, the expert agent solves an optimization problem parametric in the exogenous signal. Therefore, given examples of exogenous signals and corresponding expert actions, the goal of the learner is to learn the cost function being optimized by the expert. In this talk, we will present fundamental concepts of Inverse Optimization, novel results, as well as an application on learning to route vehicles like expert human drivers (Amazon Last Mile Routing Research Challenge). Accompanying papers: https://arxiv.org/abs/2305.07730 and https://arxiv.org/abs/2307.07357.

Video:

Slides:
Slides

Speaker: Luis Vargas (CWI)

Title: Complexity Results About the Exactness of Sum-of-Squares Approximations for Polynomial Optimization

Abstract:
A polynomial optimization problem (PoP) asks for minimizing a polynomial function over a semialgebraic set i.e., a set defined by
polynomial inequalities and equations. Polynomial optimization captures many hard problems and it is difficult to solve as expected. The Lasserre sum-of-squares hierarchy is a sequence of tractable approximations for (PoP). Under mild assumptions, this hierarchy is shown to converge asymptotically to the optimal value of (PoP). In this talk, we study the question of whether the Lasserre sum-of-squares hierarchy has finite convergence to the optimal value.  Nie (2012) shows that if the problem has finitely many minimizers and they satisfy the classical optimality conditions, then finite convergence holds. Using this, he shows that finite convergence holds generically. In this talk, we show that 1) testing whether a standard quadratic program has finitely many minimizers is NP-hard. Moreover, 2) testing whether the Lasserre hierarchy of a polynomial optimization problem has finite convergence is NP-hard.

Video:

Slides:
Slides

Speaker: Leo van Iersel (TU Delft)

Title:

Embedding phylogenetic trees in networks of low treewidth

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract:

Speaker: Danish Kashaev (CWI) and Arash Pourdamghani (TU Berlin) 

Title:

Danish Kashaev: Round and Bipartize for Vertex Cover Approximation

Arash Pourdamghani: SeedTree: A Dynamically Optimal and Local Self-Adjusting Tree

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract of "Round and Bipartize for Vertex Cover Approximation" (Danish Kashaev):
The vertex cover problem is a fundamental and widely studied NP-Hard combinatorial optimization problem. It is known that its standard linear programming relaxation is integral for bipartite graphs and half-integral for general graphs. As a consequence, the natural rounding algorithm based on this relaxation computes an optimal solution for bipartite graphs and a 2-approximation for general graphs. This 2-approximation cannot be improved in the worst-case if the unique games conjecture is true.

In this talk, we present a simple rounding algorithm based on the standard relaxation which has additional access to an odd cycle transversal (i.e. a set of vertices whose removal leaves the graph bipartite) and analyze its approximation guarantee. The motivation for studying this setting comes from an interest in interpolating the rounding curve of the standard LP in a beyond the worst-case manner, depending on how close the graph is to being bipartite. A key parameter determining tight bounds on the approximation ratio turns out to be the odd girth of the graph, defined as the length of the shortest odd cycle. We also show optimality of the analysis and discuss algorithmic applications in order to find good odd cycle transversals.

Based on https://arxiv.org/abs/2211.01699.

Video of the talk of Danish Kashaev: 

Slides of the talk of Danish Kashaev:
Slides

Abstract of "SeedTree: A Dynamically Optimal and Local Self-Adjusting Tree" (Arash Pourdamghani):
The vision of developing self-adjusting networks is now a reality: programmable optical networking switches are already being used
in big tech companies such as Google and Microsoft. However, theoretical foundations are lagging behind in this area: previous methods have been designed by having fixed and limited networking resources in mind. In this talk, I first describe how we can go from self-adjusting trees to self-adjusting networks, and then focus on the new model that we are proposing that has two key differences from traditional self-adjusting trees: it allows for capacities higher than one per node, and it uses item movements instead of rotation. Given this novel model, I detail how to design a randomized constant competitive algorithm that also allows for greedy local routing. Hence the cost of our algorithm is asymptotically optimal given any input demand while ensuring local adjustments and routing.

Based on https://arxiv.org/pdf/2301.03074.

Video of the talk of Arash Pourdamghani:

Slides of the talk of Arash Pourdamghani:  
Slides

Speaker: Anupam Gupta (Carnegie Mellon University)

Title:

Two (More) Algorithms for Set Cover

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract:

Schedule:

2:30pm - 3:30pm: Distributed, Parallel and Dynamic Graph Algorithms (Yasamin Nazari, Vrije Universiteit Amsterdam)

3:30pm - 4:00pm: Coffee Break

4:00pm - 5:00pm: An approximate solution to a 2,079,471-point traveling salesman problem (William Cook, University of Waterloo)

Registration:

As space is limited, please register using the following google form by Friday, 28 April:
https://forms.gle/n4ZPLzkuFxChPWwz7

Livestream Zoom Link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448) 

Speaker: Yasamin Nazari(Vrije Universiteit Amsterdam)

Title: Distributed, Parallel and Dynamic Graph Algorithms

Abstract:

Speaker: Harold Nieuwboer (UvA & Ruhr University Bochum) and Lucy Verberk (TU/e) 

Title:

Harold Nieuwboer: Interior-point methods on manifolds

Lucy Verberk: Stabilization of capacitated matching games

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract of "Interior-point methods on manifolds" (Harold Nieuwboer):
Interior-point methods offer a highly versatile framework for convex
optimization that is effective in theory and practice. A key notion in
their theory is that of a self-concordant barrier. We give a suitable
generalization of self-concordance to Riemannian manifolds and show that
it gives the same structural results and guarantees as in the Euclidean
setting, in particular local quadratic convergence of Newton's method.
We then analyze a short-step path-following method for optimizing
compatible objectives over a convex domain for which one has a
self-concordant barrier, and obtain the standard complexity guarantees
as in the Euclidean setting. We show that on the positive-definite
matrices and other symmetric spaces, the squared distance to a point is
a self-concordant function. Our work is motivated by recent progress on
scaling problems and non-commutative optimization, and we show that
these fit into our framework, yielding algorithms with state-of-the-art
complexity guarantees. Furthermore, we show how to apply our methods to
computing geometric medians on spaces with constant negative curvature.

Joint work with Michael Walter. Based on https://arxiv.org/abs/2303.04771.

Video of the talk of Harold Nieuwboer: 

Slides of the talk of Harold Nieuwboer:

Slides

Abstract of "Stabilization of capacitated matching games" (Lucy Verberk):
An edge-weighted, vertex-capacitated graph G is called stable if the
value of a maximum-weight capacity-matching equals the value of a
maximum-weight fractional capacity-matching. Stable graphs play a key
role in characterizing the existence of stable solutions for popular
combinatorial games that involve the structure of matchings in graphs,
such as network bargaining games and cooperative matching games.

The vertex-stabilizer problem asks to compute a minimum number of
players to block (i.e., vertices of G to remove) in order to ensure
stability for such games. The problem has been shown to be solvable in
polynomial-time, for unit-capacity graphs. This stays true also if we
impose the restriction that the set of players to block must not
intersect with a given specified maximum matching of G.

We investigate these algorithmic problems in the more general setting of
arbitrary capacities. We show that the vertex-stabilizer problem with
the additional restriction of avoiding a given maximum matching remains
polynomial-time solvable. Differently, without this restriction, the
vertex-stabilizer problem becomes NP-hard and even hard to approximate,
in contrast to the unit-capacity case.

Finally, in unit-capacity graphs there is an equivalence between the
stability of a graph, existence of a stable solution for network
bargaining games, and existence of a stable solution for cooperative
matching games. We show that this equivalence does not extend to the
capacitated case.

Joint work with Matthew Gerstbrein and Laura Sanità. Based on
https://arxiv.org/abs/2211.12179.

Video of the talk of Lucy Verberk:

Slides of the talk of Lucy Verberk:  
Slides

Speaker: Christopher Hojny (TU/e)

Title:

Relaxation Complexity: Algorithmic Possibilities and Limitations

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract:

Speaker: Jannik Matuschke (KU Leuven)

Title:

Decomposition of Probability Marginals for Security Games in Abstract Networks

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract:

Speaker: Jack Mayo (Universiteit van Amsterdam) and Isja Mannens (Universiteit Utrecht), 2 PhD talks

Title:

Jack Mayo: Scale-free Unconstrained Online Learning for Curved Losses

Isja Mannens: The parameterized complexity of the Tutte polynomial

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract of "Scale-free Unconstrained Online Learning for Curved Losses" (Jack Mayo):
A sequence of works in unconstrained online convex optimisation have investigated the possibility of adapting simultaneously to the norm U of the comparator and the maximum norm G of the gradients. In full generality, matching upper and lower bounds are known which show that this comes at the unavoidable cost of an additive GU^3, which is not needed when either G or U is known in advance. Surprisingly, recent results by Kempka et al. (2019) show that no such price for adaptivity is needed in the specific case of 1-Lipschitz losses like the hinge loss. We follow up on this observation by showing that there is in fact never a price to pay for adaptivity if we specialise to any of the other common supervised online learning losses: our results cover log loss, (linear and non-parametric) logistic regression, square loss prediction, and (linear and non-parametric) least-squares regression. We also fill in several gaps in the literature by providing matching lower bounds with an e!
 xplicit dependence on U. In all cases we obtain scale-free algorithms, which are suitably invariant under rescaling of the data. Our general goal is to establish achievable rates without concern for computational efficiency, but for linear logistic regression we also provide an adaptive method that is as efficient as the recent non-adaptive algorithm by Agarwal et al. (2021).

Video of the talk of Jack Mayo:

Slides of the talk of Jack Mayo:  
Slides

Abstract of "The parameterized complexity of the Tutte polynomial" (Isja Mannens):
The Tutte polynomial has been widely studied in various areas of mathematics and theoretical computer science. One of these areas is computational complexity. A classic result is that of Jaeger, Vertigan and Welsh, who give a complete dichotomy for the complexity of evaluating the Tutte polynomial at a given point. With recent developments in the field of parameterized complexity in mind, one might ask what such a dichotomy would look like with respect to certain graph parameters.
In this talk we will discuss unpublished work that seeks to answer this question for the parameters of treewidth, pathwidth and cutwidth. We will discuss parallels with the techniques of Jaeger, Vertigan and Welsh and how they can be adapted to this setting. Using this approach, in conjunction with existing hardness results, we find asymptotically tight bounds for all points on so called special curves H_q, for any integer valued q.
In addition, we will discuss a novel rank-based algorithm for the problem of counting forests, a specific evaluation of the Tutte polynomial. This algorithm runs in O(64^tw) time which results in a surprising asymmetry in the complexity of computing the Tutte polynomial, along the lines 'y=1' and 'x=1'. The former can be reduced to counting forests, while the latter is not solvable in O(ctw^{o(ctw)}) time under ETH.

Video of the talk of Isja Mannens: 

Slides of the talk of Isja Mannens:
Slides

Speaker: Carla Groenland (Utrecht University)

Title:

List Colouring Trees in Logspace

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract: