Events

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.

Video:

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:

Slides:

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:

On Thursday October 13, the Dutch Day of Optimization will take place; see this webpage. 

The Dutch Day on Optimization is the yearly in-person event related to the Dutch Seminar on Optimization. The main purpose of the event is to bring together the Dutch Optimization community across the areas of operations research, computer science and discrete mathematics. The event will highlight the research of both national and international speakers. The lectures will take place in the Turing Room in the Amsterdam Science Park Congress Center.

Speaker: Jesse van Rhijn (Universiteit Twente) and Sander Borst (Centrum Wiskunde & Informatica)

Title:

Jesse van Rhijn: Towards a Lower Bound for the Average Case Runtime of Simulated Annealing on TSP

Sander Borst: Selection in explorable heaps

Zoom link: 

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

Abstract of "Towards a Lower Bound for the Average Case Runtime of Simulated Annealing on TSP" (Jesse van Rhijn):
We analyze simulated annealing (SA) for simple randomized instances of the Traveling Salesperson Problem. Our analysis shows that the theoretically optimal cooling schedule of Hajek explores members of the solution set which are in expectation far from the global optimum. We obtain a lower bound on the expected length of the final tour obtained by SA on these random instances. In addition, we also obtain an upper bound on the expected value of its variance. These bounds assume that the Markov chain that describes SA is stationary, a situation that does not truly hold in practice. Hence, we also formulate conditions under which the bounds extend to the nonstationary case. These bounds are obtained by comparing the tour length distribution to a related distribution. We furthermore provide numerical evidence for a stochastic dominance relation that appears to exist between these two distributions, and formulate a conjecture in this direction. If proved, this conjecture implies that SA stays far from the global optimum with high probability when executed for any sub-exponential number of iterations. This would show that SA requires at least exponentially many iterations to reach a global optimum with nonvanishing probability.

Video of the talk of Jesse van Rhijn:

Slides of the talk of Jesse van Rhijn:  
Slides

Abstract of "Selection in explorable heaps" (Sander Borst):
Explorable heap selection is the problem of selecting the nth smallest value in a binary heap, where the values can only be accessed by traversing the binary tree. In this setting we want to minimize the distance traveled in the tree. The problem is related to the node selection problem for the branch-and-bound algorithm.
The problem was originally proposed by Karp, Saks and Widgerson (FOCS '86), who also proposed algorithms for this problem. Recently we found a new algorithm, that improves on the running time. In this talk I will explain the problem, our new algorithm and the connection between the problem and branch-and-bound.

Video of the talk of Sander Borst: 

Slides of the talk of Sander Borst:
Slides

Speaker: Ilker Birbil (Universiteit van Amsterdam)

Title:

Counterfactual Explanations Using Optimization With Constraint Learning

Zoom link: 

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

Abstract:

Speaker: Vera Traub (ETH Zürich)

Title:

Better-Than-2 Approximations for Weighted Tree Augmentation and Forest Augmentation

Zoom link: 

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

Abstract:

Video:

Slides: 

Slides