Events
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:
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:
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.
Seminar: Jesse van Rhijn (Universiteit Twente) and Sander Borst (CWI), 2 PhD talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-2-phd-talks-september-2022
- Seminar: Jesse van Rhijn (Universiteit Twente) and Sander Borst (CWI), 2 PhD talks
- 2022-09-29T16:00:00+02:00
- 2022-09-29T17:00:00+02:00
- When Sep 29, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Where Online seminar
- Contact Name Daniel Dadush and Sven Polak
- Web Visit external website
- Add event to calendar iCal
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
Seminar: Ilker Birbil (Universiteit van Amsterdam)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-ilker-birbil-universiteit-van-amsterdam
- Seminar: Ilker Birbil (Universiteit van Amsterdam)
- 2022-08-25T16:00:00+02:00
- 2022-08-25T17:00:00+02:00
- When Aug 25, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Where Online seminar
- Contact Name Daniel Dadush and Sven Polak
- Web Visit external website
- Add event to calendar iCal
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:
Video:
Slides:
Seminar: Vera Traub (ETH Zürich)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-vera-traub-eth-zurich
- Seminar: Vera Traub (ETH Zürich)
- 2022-06-30T16:00:00+02:00
- 2022-06-30T17:00:00+02:00
- When Jun 30, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Where Online seminar
- Contact Name Daniel Dadush and Sven Polak
- Web Visit external website
- Add event to calendar iCal
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:
In the second part of the talk we show how this algorithm can be used to obtain the first better-than-2 approximation algorithm for the Forest Augmentation Problem. In this problem we want to choose a minimum number of edges, among a given set of options, that we can add to a graph G to make it 2-edge connected. In contrast to the Tree Augmentation Problem, we do not require the given graph G to be connected.
This talk is based on joint works with Fabrizio Grandoni, Afrouz Jabal Ameli, and Rico Zenklusen.
Video:
Slides:
Seminar: Jasper van Doornmalen (TU Eindhoven) + Daniel Brosch (Tilburg University), 2 PhD talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-2-phd-talks-1
- Seminar: Jasper van Doornmalen (TU Eindhoven) + Daniel Brosch (Tilburg University), 2 PhD talks
- 2022-05-24T16:00:00+02:00
- 2022-05-24T17:00:00+02:00
- When May 24, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Add event to calendar iCal
Speaker: Jasper van Doornmalen (TU/e) and Daniel Brosch (Tilburg University)
Title:
Jasper van Doornmalen: Symmetry handling in binary programs through propagation
Daniel Brosch : The Symmetries of Flag-Algebras
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract of "Symmetry handling in binary programs through propagation" (Jasper van Doornmalen):
Symmetries of binary programs are known to dramatically slow down branch-and-bound procedures. A classical approach to handle permutation symmetries is to enforce that only one representative of equivalent (symmetric) solutions can be computed. In classical integer programming literature, among others, this is established by introducing symmetry handling constraints. This way, solutions that are not lexicographically maximal among the permuted solutions are cut off.
We present a propagation-based symmetry handling technique. Given a set of fixed variables (e.g., due to branching decisions), this technique identifies further variables that can be fixed to ensure that only lexicographically maximal solutions are computed. We present efficient algorithms to find such additional symmetry-based variable fixings for arbitrary sets of permutations and cyclic groups. In particular, for cyclic groups, we show that all possible fixings can be found in polynomial time even if the cyclic group has exponential order.
Our methods are implemented as a plugin in the academic integer programming solver SCIP, and we discuss the effectiveness of these methods on various symmetrical instances.
Video of the talk of Jasper van Doornmalen:
Slides of the talk of Jasper van Doornmalen:
Slides
Abstract of "The Symmetries of Flag-Algebras" (Daniel Brosch):
Flag-Algebras, first introduced by Razborov in 2007, remain one of the most powerful tools in extremal combinatorics. Recently a connection to polynomial optimization was discovered: We can recover Flag-Sums-of-Squares hierarchies by partially exploiting the symmetries of a polynomial optimization hierarchy. We continue from there and fully exploit the symmetries in this polynomial setting for two different hierarchies, one focusing on a low number of edges, and another focusing on a low number of vertices of appearing Flags. For the first, due to the high initial dimension of the hierarchy, a novel algorithm was needed to decompose modules of the symmetric group into irreducible submodules. We apply the reduced hierarchies to obtain outer approximations of graph-profiles, which model various open problems from extremal combinatorics.
Video of the talk of Daniel Brosch:
Slides of the talk of Daniel Brosch:
Link to Daniel's slides on his webpage
Seminar: Krzysztof Postek (TU Delft)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-krzysztof-postek-tu-delft
- Seminar: Krzysztof Postek (TU Delft)
- 2022-04-28T16:00:00+02:00
- 2022-04-28T17:00:00+02:00
- When Apr 28, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Where Online seminar
- Contact Name Daniel Dadush and Sven Polak
- Add event to calendar iCal
Speaker: Krzysztof Postek (TU Delft)
Title:
An Adaptive Robust Optimization Model for Parallel Machine Scheduling
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
We develop an approach that takes into account, at the beginning of the planning horizon, the possibility that scheduling decisions can be adjusted, allowing an arbitrary set of scenarios for the task lengths' realizations. We demonstrate that this can lead to better here-and-now decisions. In a recent work, we develop an exact MILP formulation of this problem for discrete sets of scenarios, which, to best of our knowledge, is the first one in which so-called nonanticipativity constraints are formulated exactly.
Joint work with Shimrit Shtern (Technion), Izack Cohen (Bar Ilan University), Izak de Heer (TU Delft).
Video:
Slides:
Slides
Seminar: Esteban Gabory (CWI) + Donato Maragno (UvA), 2 PhD talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-2-phd-talks
- Seminar: Esteban Gabory (CWI) + Donato Maragno (UvA), 2 PhD talks
- 2022-03-31T16:00:00+02:00
- 2022-03-31T17:00:00+02:00
- When Mar 31, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Add event to calendar iCal
Speaker: Esteban Gabory (CWI) + Donato Maragno (UvA)
Title:
Esteban Gabory: On Strings Having the Same Length-k Substrings
Donato Maragno : Mixed-Integer Optimization with Constraint Learning
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract of "On Strings Having the Same Length-k Substrings" (Esteban Gabory):
Video of the talk of Esteban Gabory:
Slides of the talk of Esteban Gabory:
Slides
Abstract of "Mixed-Integer Optimization with Constraint Learning" (Donato Maragno):
Joint work with: Holly Wiberg, Dimitris Bertsimas, S. Ilker Birbil, Dick den Hertog, Adejuyigbe Fajemisin
Paper:
https://arxiv.org/abs/2111.04469
Code:
https://github.com/hwiberg/OptiCL
Video of the talk of Donato Maragno:
Slides of the talk of Donato Maragno:
Slides
Seminar: Friedrich Eisenbrand (EPFL Lausanne), International speaker
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-friedrich-eisenbrand-epfl-lausanne-international-speaker
- Seminar: Friedrich Eisenbrand (EPFL Lausanne), International speaker
- 2022-03-03T16:00:00+01:00
- 2022-03-03T17:00:00+01:00
- When Mar 03, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Add event to calendar iCal
Speaker: Friedrich Eisenbrand (EPFL Lausanne)
Title:
Algorithms for Integer Programming
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
Video:
Slides:
Slides