Events
Seminar: Nando Leijenhorst (TU Delft) and Artem Tsikiridis (CWI)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-nando-leijenhorst-tu-delft-and-artem-tsikiridis-cwi
- Seminar: Nando Leijenhorst (TU Delft) and Artem Tsikiridis (CWI)
- 2024-10-31T16:00:00+01:00
- 2024-10-31T17:00:00+01:00
- When Oct 31, 2024 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Where Online seminar
- Contact Name Daniel Dadush and Cedric Koh
- Web Visit external website
- Add event to calendar iCal
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:
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:
Seminar: Neil Olver (LSE)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-neil-olver-lse
- Seminar: Neil Olver (LSE)
- 2024-09-26T16:00:00+02:00
- 2024-09-26T17:00:00+02:00
- When Sep 26, 2024 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Where Hybrid Seminar: L016@CWI and Online
- Contact Name Daniel Dadush and Cedric Koh
- Web Visit external website
- Add event to calendar iCal
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:
Seminar: Aida Khajavirad (Lehigh University)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-aida-khajavirad-lehigh-university
- Seminar: Aida Khajavirad (Lehigh University)
- 2024-09-12T16:00:00+02:00
- 2024-09-12T17:00:00+02:00
- When Sep 12, 2024 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Where Online
- Contact Name Daniel Dadush and Cedric Koh
- Web Visit external website
- Add event to calendar iCal
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
Seminar: Caroline Jagtenberg (VU Amsterdam)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-caroline-jagtenberg-vu-amsterdam
- Seminar: Caroline Jagtenberg (VU Amsterdam)
- 2024-04-23T16:00:00+02:00
- 2024-04-23T17:00:00+02:00
- When Apr 23, 2024 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Where Hybrid Seminar: L016@CWI and Online
- Contact Name Daniel Dadush and Cedric Koh
- Web Visit external website
- Add event to calendar iCal
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
Seminar: Alireza Yazdani (TU Eindhoven) and Jesse van Rhijn (University of Twente), 2 PhD-talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-alireza-yazdani-tu-eindhoven-and-jesse-van-rhijn-university-of-twente-2-phd-talks
- Seminar: Alireza Yazdani (TU Eindhoven) and Jesse van Rhijn (University of Twente), 2 PhD-talks
- 2024-03-26T16:00:00+01:00
- 2024-03-26T17:00:00+01:00
- When Mar 26, 2024 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Where Online seminar
- Contact Name Daniel Dadush and Cedric Koh
- Web Visit external website
- Add event to calendar iCal
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
Seminar: Sami Davies (Simons Institute & UC Berkeley)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-sami-davies-simons-institute-uc-berkeley
- Seminar: Sami Davies (Simons Institute & UC Berkeley)
- 2024-02-29T16:00:00+01:00
- 2024-02-29T17:00:00+01:00
- When Feb 29, 2024 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Where Online Seminar
- Contact Name Daniel Dadush and Cedric Koh
- Web Visit external website
- Add event to calendar iCal
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:
Seminar: Frank Vallentin (University of Cologne)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-frank-vallentin-university-of-cologne
- Seminar: Frank Vallentin (University of Cologne)
- 2024-01-25T16:00:00+01:00
- 2024-01-25T17:00:00+01:00
- When Jan 25, 2024 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Where Hybrid Seminar: L016@CWI and Online
- Contact Name Daniel Dadush and Cedric Koh
- Web Visit external website
- Add event to calendar iCal
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
Seminar: Hilde Verbeek (CWI) and Bram Bekker (TU Delft), 2 PhD Talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/hilde-verbeek-cwi-and-bram-bekker-tu-delft-2-phd-talks
- Seminar: Hilde Verbeek (CWI) and Bram Bekker (TU Delft), 2 PhD Talks
- 2023-12-07T16:00:00+01:00
- 2023-12-07T17:00:00+01:00
- When Dec 07, 2023 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Where Online Seminar
- Contact Name Daniel Dadush and Cedric Koh
- Web Visit external website
- Add event to calendar iCal
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
Seminar: Stefanie Jegelka (MIT)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-stefanie-jegelka-mit
- Seminar: Stefanie Jegelka (MIT)
- 2023-10-19T16:00:00+02:00
- 2023-10-19T17:00:00+02:00
- When Oct 19, 2023 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Where Online seminar
- Contact Name Daniel Dadush and Cedric Koh
- Web Visit external website
- Add event to calendar iCal
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:
Seminar: Pedro Zattoni Scroccaro (TU Delft) and Luis Vargas (CWI), 2 PhD-talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-pedro-zattoni-scroccaro-tu-delft-and-luis-vargas-cwi-2-phd-talks
- Seminar: Pedro Zattoni Scroccaro (TU Delft) and Luis Vargas (CWI), 2 PhD-talks
- 2023-09-28T16:00:00+02:00
- 2023-09-28T17:00:00+02:00
- When Sep 28, 2023 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Where Online seminar
- Contact Name Daniel Dadush and Cedric Koh
- Web Visit external website
- Add event to calendar iCal
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
Seminar: Leo van Iersel (TU Delft)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-leo-van-iersel-tu-delft
- Seminar: Leo van Iersel (TU Delft)
- 2023-08-31T16:00:00+02:00
- 2023-08-31T17:00:00+02:00
- When Aug 31, 2023 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Where Online seminar
- Contact Name Daniel Dadush and Cedric Koh
- Web Visit external website
- Add event to calendar iCal
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:
Seminar: Danish Kashaev (CWI) and Arash Pourdamghani (TU Berlin), 2 PhD-talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-danish-kashaev-cwi-and-arash-pourdamghani-tu-berlin-2-phd-talks
- Seminar: Danish Kashaev (CWI) and Arash Pourdamghani (TU Berlin), 2 PhD-talks
- 2023-06-29T16:00:00+02:00
- 2023-06-29T17:00:00+02:00
- When Jun 29, 2023 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Where Online seminar
- Contact Name Daniel Dadush and Cedric Koh
- Web Visit external website
- Add event to calendar iCal
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
Seminar: Anupam Gupta (Carnegie Mellon University)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-anupam-gupta-carnegie-mellon-university
- Seminar: Anupam Gupta (Carnegie Mellon University)
- 2023-05-23T16:00:00+02:00
- 2023-05-23T17:00:00+02:00
- When May 23, 2023 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Where Online seminar
- Contact Name Daniel Dadush, Cedric Koh, and Sven Polak
- Web Visit external website
- Add event to calendar iCal
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:
the goal is to find a collection of sets with minimum cost whose union
covers the universe. This NP-hard problem has long been known to admit
logarithmic approximations. Moreover, the logarithmic guarantee is tight,
unless P=NP. In this talk I will present two new algorithms which also get
logarithmic guarantees. These algorithms came out of attempts to get
refined guarantees for set cover in beyond-worst-case settings.
The talk is based on joint works with Greg Kehne (CMU and Harvard),
Euiwoong Lee (U. Michigan), Roie Levin (CMU and Tel Aviv U), and Jason Li
(CMU and Simons/Berkeley).
Video:
Intercity Seminar
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/intercity-seminar
- Intercity Seminar
- 2023-05-04T14:30:00+02:00
- 2023-05-04T17:00:00+02:00
- When May 04, 2023 from 02:30 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Where Room L017 at CWI
- Contact Name Daniel Dadush
- Add event to calendar iCal
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:
algorithms in models that capture different aspects of modern computational
systems and big data processing. This talk focuses on graph algorithms in
several such models, such as distributed, dynamic and parallel models.
We will focus on the task of graph distance computation in these models and
introduce several graph theoretic structures that preserve
approximate distances, but tradeoff this approximation factor with size,
query time, or the number of hops on the approximate shortest paths. We
then show how these combinatorial structures can be utilized for
faster distance computation in distributed or dynamic settings.
Finally, we discuss several open problems including possible connections
with combinatorial optimization.
Title: An approximate solution to a 2,079,471-point traveling salesman problem
Abstract:
of 2,079,471 stars. We discuss how linear programming allows us to prove the
tour is at most a factor of 0.0000074 longer than an optimal solution. The talk
will focus on the use of GF(2) linear systems to drive the cutting-plane method
towards improved LP relaxations of the TSP.
Video:
Seminar: Harold Nieuwboer (UvA & Ruhr University Bochum) and Lucy Verberk (TU/e), 2 PhD-talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-harold-nieuwboer-uva-ruhr-university-bochum-and-lucy-verberk-tu-e-2-phd-talks
- Seminar: Harold Nieuwboer (UvA & Ruhr University Bochum) and Lucy Verberk (TU/e), 2 PhD-talks
- 2023-03-30T16:00:00+02:00
- 2023-03-30T17:00:00+02:00
- When Mar 30, 2023 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Where Online seminar
- Contact Name Daniel Dadush, Cedric Koh, and Sven Polak
- Web Visit external website
- Add event to calendar iCal
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
Seminar: Christopher Hojny (TU/e)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-christopher-hojny-tu-e
- Seminar: Christopher Hojny (TU/e)
- 2023-02-23T16:00:00+01:00
- 2023-02-23T17:00:00+01:00
- When Feb 23, 2023 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Where Online seminar
- Contact Name Daniel Dadush and Sven Polak
- Web Visit external website
- Add event to calendar iCal
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:
complexity rc(X) is the smallest number of facets of any polyhedron P
such that the integer points in P coincide with X. It is a useful tool
to investigate the existence of compact linear descriptions of X. In
particular, it provides the minimum number of inequalities needed in any
integer programming formulation of X. Moreover, when restricting the
polyhedra P to be rational, rc_Q(X) denotes the corresponding rational
relaxation complexity of X.
In this presentation, I discuss several algorithmic aspects of finding
the relaxation complexity. First, a natural question is whether rc(X) is
actually computable. While this question is notoriously open in general,
I present an algorithm that finds rc(X) in dimension 2. Second, rc_Q(X)
is an upper bound on rc(X). A natural idea is thus to provide computable
lower bounds on rc(X) and computable upper bounds on rc_Q(X). If these
bounds match, rc(X) and rc_Q(X) have been found. I show that we can
indeed find a matching upper bound on rc_Q(X), whereas I discuss why
finding a matching lower bound for rc(X) seems to be more challenging.
Finally, the previously sketched idea only allows to compute rc(X) and
rc_Q(X) if both quantities coincide. I conclude this presentation by a
brief outline that rc(X) can be strictly smaller than rc_Q(X).
Video:
Slides:
Slides
Seminar: Jannik Matuschke (KU Leuven)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-jannik-matuschke-ku-leuven
- Seminar: Jannik Matuschke (KU Leuven)
- 2023-01-26T16:00:00+01:00
- 2023-01-26T17:00:00+01:00
- When Jan 26, 2023 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Where Online seminar
- Contact Name Daniel Dadush and Sven Polak
- Web Visit external website
- Add event to calendar iCal
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:
system is equipped with a required hitting probability r(P) and each
element e of E has a probability marginal p(e). We study the question
whether the marginals can be decomposed into a distribution over all
subsets of E such that the resulting random set intersects each set P from
the system with probability at least r(P). A simple necessary condition is
that for every set P in the system, the sum of the marginals of elements in
P is at least r(P).
Extending a result by Dahan, Amin, and Jaillet (Mathematics of Operations
Research 47:457-484, 2022) motivated by a security game in a directed
acyclic graph, we show that the aforementioned necessary condition is is
also sufficient in the following two settings: (i) the set system fulfills
a max-flow/min-cut property and the requirements are affine; (ii) the set
system is an abstract network and the requirements fulfill a weak
conservation law. We provide algorithms for the computation of the
corresponding decompositions and, in some cases, simple explicit
descriptions of these decompositions. As a subroutine, we also devise a
combinatorial algorithm for computing shortest paths in abstract networks,
answering an open question by McCormick (SODA 1996). A consequence of our
results is that equilibria for the security game studied by Dahan et al.
(2022) and similar games involving randomized surveillance strategies can
be computed efficiently, even when the underlying digraph contains cycles.
Video:
Slides:
Slides
Seminar: Jack Mayo (University of Amsterdam) and Isja Mannens (Utrecht University), 2 PhD talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-jack-mayo-university-of-amsterdam-and-isja-mannens-utrecht-university-2-phd-talks
- Seminar: Jack Mayo (University of Amsterdam) and Isja Mannens (Utrecht University), 2 PhD talks
- 2022-12-08T16:00:00+01:00
- 2022-12-08T17:00:00+01:00
- When Dec 08, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Where Online seminar
- Contact Name Daniel Dadush and Sven Polak
- Web Visit external website
- Add event to calendar iCal
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
Seminar: Carla Groenland (Utrecht University)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-carla-groenland-utrecht-university
- Seminar: Carla Groenland (Utrecht University)
- 2022-11-22T16:00:00+01:00
- 2022-11-22T17:00:00+01:00
- When Nov 22, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Where Online seminar, possible to watch in L0.17 at CWI
- Contact Name Daniel Dadush and Sven Polak
- Web Visit external website
- Add event to calendar iCal
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:
This talk is primarily based on joint work with Hans Bodlaender and Hugo Jacob.
Video:
Slides:
Dutch Day of Optimization
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/dutch-day-of-optimization
- Dutch Day of Optimization
- 2022-10-13T00:00:00+02:00
- 2022-10-13T23:59:59+02:00
- When Oct 13, 2022 (Europe/Amsterdam / UTC200)
- Where Amsterdam Science Park Congress Center, Science Park 125, 1098 XG Amsterdam
- Contact Name Daniel Dadush
- Web Visit external website
- Add event to calendar iCal
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.