Events
Seminar: Andreas Wiese (Vrije Universiteit Amsterdam)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-andreas-wiese-vrije-universiteit
- Seminar: Andreas Wiese (Vrije Universiteit Amsterdam)
- 2022-01-27T16:00:00+01:00
- 2022-01-27T17:00:00+01:00
- When Jan 27, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Add event to calendar iCal
Speaker: Andreas Wiese (VU Amsterdam)
Title:
A PTAS for the Unsplittable Flow on a Path problem
(joint work with Fabrizio Grandoni and Tobias Mömke)
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
In this talk, we present a polynomial time $(1+\eps)$-approximation algorithm for UFP.
Video:
[Will be inserted after the talk]
Slides:
[Will be inserted after the talk]
Seminar: Hadi Abbaszadehpeivasti (Tilburg) + Utku Karaca (Erasmus University), 2 PhD talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-hadi-abbaszadehpeivasti-tilburg-utku-karaca-erasmus-university-2-phd-talks
- Seminar: Hadi Abbaszadehpeivasti (Tilburg) + Utku Karaca (Erasmus University), 2 PhD talks
- 2021-12-09T16:00:00+01:00
- 2021-12-09T17:00:00+01:00
- When Dec 09, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Add event to calendar iCal
Speaker: Hadi Abbaszadehpeivasti (Tilburg University) + Utku Karaca (Erasmus University)
Title:
Hadi Abbaszadehpeivasti: On the convergence rate of DCA
Utku Karaca : Differentially Private Resource Sharing
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract of "On the convergence rate of DCA" (Hadi Abbaszadehpeivasti):
https://arxiv.org/abs/2109.13566
Video of the talk of Hadi Abbaszadehpeivasti:
Slides of the talk of Hadi Abbaszadehpeivasti:
Abstract of "Differentially Private Resource Sharing" (Utku Karaca):
This study examines a resource-sharing problem involving multiple parties that agree to use a set of capacities together. We start with modeling the whole problem as a mathematical program, where all parties are required to exchange information to obtain the optimal objective function value. This information bears private data from each party in terms of coefficients used in the mathematical program. Moreover, the parties also consider the individual optimal solutions as private. In this setting, the great concern for the parties is the privacy of their data and their optimal allocations. Methodology and results: We propose a two-step approach to meet the privacy requirements of the parties. In the first step, we obtain a reformulated model that is amenable to a decomposition scheme. Although this scheme eliminates almost all data exchange, it does not provide a formal privacy guarantee. In the second step, we provide this guarantee with a differentially private algorithm at the expense of deviating slightly from the optimality. We provide bounds on this deviation and discuss the consequences of these theoretical results. The study ends with a simulation study on a planning problem that demonstrates an application of the proposed approach. Managerial implications: Our work provides a new optimization model and a solution approach for optimal allocation of a set of shared resources among multiple parties who expect privacy of their data. The proposed approach is based on the decomposition of the shared resources and the randomization of the optimization iterations. With our analysis, we show that the resulting randomized algorithm does give a guarantee for the privacy of each party's data. As we work with a general optimization model, our analysis and discussion can be used in different application areas including production planning, logistics, and network revenue management.
https://arxiv.org/abs/2102.07178
Video of the talk of Utku Karaca:
Slides of the talk of Utku Karaca:
Seminar: Britta Peis (RWTH Aachen University), International speaker
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-britta-peis-rwth-aachen-university-international-speaker
- Seminar: Britta Peis (RWTH Aachen University), International speaker
- 2021-11-23T16:00:00+01:00
- 2021-11-23T17:00:00+01:00
- When Nov 23, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Add event to calendar iCal
Speaker: Britta Peis (RWTH Aachen)
Title:
Primal-dual approximation framework for weighted integer covering problems.
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
Video:
Slides:
Seminar: Lucas Slot (CWI) + Juan José Maulén (Groningen), 2 PhD talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-lucas-slot-cwi-juan-jose-maulen-groningen-2-phd-talks
- Seminar: Lucas Slot (CWI) + Juan José Maulén (Groningen), 2 PhD talks
- 2021-10-28T16:00:00+02:00
- 2021-10-28T17:00:00+02:00
- When Oct 28, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Web Visit external website
- Add event to calendar iCal
Speaker: Lucas Slot (CWI Amsterdam) + Juan José Maulén (RU Groningen)
Title:
Lucas Slot: Degree bounds for positivity certificates and the polynomial kernel method
Juan José Maulén: Acceleration of fixed point algorithms via inertia
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract of "Degree bounds for positivity certificates and the polynomial kernel method" (Lucas Slot):
We apply the PKM to additional sets, including the binary hypercube {-1, 1}^n, the unit box [-1, 1]^n and the unit ball.
This is based on joint work with Monique Laurent.
Arxiv link: https://arxiv.org/abs/2011.04027
Video of the talk of Lucas Slot:
Slides of the talk of Lucas Slot:
Abstract of "Acceleration of fixed point algorithms via inertia" (Juan José Maulén):
In this talk, we will use the results about the convergence of inertial optimization algorithms, defined as fixed point iterations from a family of cocoercive operators. This result implies that exists inertial versions of the Primal-dual splitting algorithm proposed by Briceño and Roldan on 2019, and for the three-operator splitting scheme proposed by Davis and Yin on 2015. Both algorithms fit on the framework of optimization algorithms defined by cocoercive operators. The inertial versions obtained are tested in several numerical experiments, where better performance with respect to the original algorithms can be observed.
Video of the talk of Juan José Maulén:
Slides of the talk of Juan José Maulén:
Seminar: Martin Skutella (TU Berlin), International speaker
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-martin-skutella-tu-berlin-international-speaker
- Seminar: Martin Skutella (TU Berlin), International speaker
- 2021-09-30T16:00:00+02:00
- 2021-09-30T17:00:00+02:00
- When Sep 30, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Add event to calendar iCal
Speaker: Martin Skutella (TU Berlin)
Title:
A Faster Algorithm for Quickest Transshipments via an Extended Discrete Newton Method
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
Video:
Slides:
Seminar: Samuel Fiorini (Bruxelles), International speaker
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-samuel-fiorini-bruxelles-international-speaker
- Seminar: Samuel Fiorini (Bruxelles), International speaker
- 2021-08-26T16:00:00+02:00
- 2021-08-26T17:00:00+02:00
- When Aug 26, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Add event to calendar iCal
Speaker: Samuel Fiorini (Université libre de Bruxelles)
Title:
Integer programs with bounded subdeterminants and two nonzeros per row
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
Video:
Slides:
Seminar: Lightning Talks (several speakers)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-lightning-talks-several-speakers
- Seminar: Lightning Talks (several speakers)
- 2021-06-24T16:00:00+02:00
- 2021-06-24T17:00:00+02:00
- When Jun 24, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Add event to calendar iCal
Speaker: Several speakers (hopefully 12-15)
Title: Lightning Talks
Lightning talks are 1 to 5 min talks meant to foster interaction in the community. This can include:
1. Introducing yourself & what you do
2. Announcing a recent result & why its cool
3. Posing an open problem / advertising a research area (or an open position)
4. Anything awesome you want to tell us about :)
If you'd like to sign up for a talk, please add your name and a tentative title here:
https://docs.google.com/spreadsheets/d/1YebbULLoO6FmIrOcEdkA_3pzePLe0pWj2lQCvvKwdA8/edit?usp=sharing
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Our goal is to include as many people as possible, so we'll try and fit everyone.
Seminar: Celine Swennenhuis (Eindhoven) + Sophie Huiberts (CWI), 2 PhD talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-celine-swennenhuis-eindhoven-sophie-huiberts-cwi-2-phd-talks
- Seminar: Celine Swennenhuis (Eindhoven) + Sophie Huiberts (CWI), 2 PhD talks
- 2021-05-27T16:00:00+02:00
- 2021-05-27T17:00:00+02:00
- When May 27, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Add event to calendar iCal
Speaker: Céline Swennenhuis (TU Eindhoven) + Sophie Huiberts (CWI)
Title:
Céline Swennenhuis: A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins
Sophie Huiberts: Combinatorial Diameter of Random Polytopes
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract of "A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins" (Céline Swennenhuis):
Björklund, Husfeldt and Koivisto (SICOMP 2009) presented an O(2^n) time algorithm for Bin Packing. In this paper we show that for every m there exists a constant s_m > 0 such that an instance of Bin Packing with m bins can be solved in O((2-s_m)^n) time.
Video of the talk of Céline Swennenhuis:
Slides of the talk of Céline Swennenhuis:
Abstract of "Combinatorial Diameter of Random Polytopes" (Sophie Huiberts):
The combinatorial diameter of a polytope is the maximum shortest path between any two vertices of the polytope, in the graph consisting of that polytope's vertices and edges. This diameter is closely related to the simplex method for linear programming and has been studied since the 1950's, when Hirsch asked in a letter to Dantzig whether the combinatorial diameter of a polytope in R^n with m facets has diameter at most m-n.
In this paper we study random polytopes, either the intersection of random halfspaces or the convex hull of random vectors, chosen from the unit sphere. In the first case, we prove that the diameter is between Omega(m)^{1/(n-1)} and O( (4√2)^n m^1/(n-1)) with high probability up to logarithmic factors. In the second case, we prove that the diameter is between Omega(m)^{1/(n-1)} and O( (√2)^n m^1/(n-1)) with high probability up to logarithmic factors.
Video of the talk of Sophie Huiberts:
Notes of the talk of Sophie Huiberts, the website with polytopes, and a nice twitter abstract:
Seminar: Juan Peypouquet (RU Groningen)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-juan-peypouquet-groningen
- Seminar: Juan Peypouquet (RU Groningen)
- 2021-04-29T16:00:00+02:00
- 2021-04-29T17:00:00+02:00
- When Apr 29, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Add event to calendar iCal
Speaker: Juan Peypouquet (RU Groningen)
Title:
Function Curvature and Algorithm Complexity in Convex Optimization
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
impact on the complexity of optimization algorithms. In this talk, we will
present some basic concepts related to function curvature and discuss their
relationship with descent properties and convergence rates of first-order
methods.
Video:
Slides:
Seminar: Moritz Buchem (Maastricht) + Michelle Sweering (CWI)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-moritz-buchem-maastricht-michelle-sweering-cwi-2-phd-talks
- Seminar: Moritz Buchem (Maastricht) + Michelle Sweering (CWI)
- 2021-03-25T16:00:00+01:00
- 2021-03-25T17:00:00+01:00
- When Mar 25, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Add event to calendar iCal
Speaker: Moritz Buchem (Maastricht) + Michelle Sweering (CWI), 2 PhD talks
Title:
Moritz Buchem: Additive Approximation Schemes for Load Balancing problems
Michelle Sweering: On Breaking k-Trusses
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract of "Additive Approximation Schemes for Load Balancing problems" (Moritz Buchem):
Additive approximation schemes compute a solution with an absolute error in the objective of at most εh for some suitable parameter h and any given ε > 0. We consider the problem of assigning jobs to identical machines with respect to common load balancing objectives like makespan minimization, the Santa Claus problem (on identical machines), and the envy-minimizing Santa Claus problem. For these settings we present additive approximation schemes for h = pmax, the maximum processing time of the jobs.
Our technical contribution is two-fold. First, we introduce a new relaxation based on integrally assigning slots
to machines and fractionally assigning jobs to the slots. We refer to this relaxation as the slot-MILP. While it has a linear number of integral variables, we identify structural properties of (near-)optimal solutions, which allow us to compute those in polynomial time. The second technical contribution is a local-search algorithm which rounds any given solution to the slot-MILP, introducing an additive error on the machine loads of at most εpmax.
This is joint work together with Lars Rohwedder (EPFL), Tjark Vredeveld (UM) and Andreas Wiese (UChile).
Video of the talk of Moritz Buchem:
Slides of the talk of Moritz Buchem:
Abstract of "On Breaking k-Trusses" (Michelle Sweering):
This talk is about breaking communities in networks, specifically k-trusses.
A subgraph H of G is a k-truss if each edge of H is contained in at least k-2 triangles in H.
We discuss how to break k-trusses by deleting as few edges as possible.
Since the problem of breaking k-trusses is NP-hard and even hard to approximate, we also give various heuristics.
Video of the talk of Michelle Sweering:
Slides of the talk of Michelle Sweering:
Seminar: Santanu Dey (Georgia Tech)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-santanu-dey-georgia-tech-international-speaker
- Seminar: Santanu Dey (Georgia Tech)
- 2021-02-25T16:00:00+01:00
- 2021-02-25T17:00:00+01:00
- When Feb 25, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Add event to calendar iCal
Speaker: Santanu Dey (Georgia Tech)
Title: Sparse PSD approximation of the PSD cone
Zoom link: https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract: While semidefinite programming (SDP) problems are polynomially solvable in theory, it is often difficult to solve large SDP instances in practice. One computational technique used to address this issue is to relax the global positive-semidefiniteness (PSD) constraint and only enforce PSD-ness on smaller k × k principal submatrices — we call this the sparse SDP relaxation. Surprisingly, it has been observed empirically that in some cases this approach appears to produce bounds that are close to the optimal objective function value of the original SDP.
In this talk, we formally attempt to compare the strength of the sparse SDP relaxation vis-`a-vis the original SDP from a theoretical perspective. In order to simplify the question, we arrive at a data independent version of it, where we compare the sizes of SDP cone and the k-PSD closure, which is the cone of matrices where PSDness is enforced on all k × k principal submatrices. In particular, we investigate the question of how far a matrix of unit Frobenius norm in the k-PSD closure can be from the SDP cone. We provide two incomparable upper bounds on this farthest distance as a function of k and n. We also provide matching lower bounds, which show that the upper bounds are tight within a constant in different regimes of k and n.
Other than linear algebra techniques, we use probabilistic methods to arrive at these bounds. Two other key ingredients are: (i) observing that the hyperbolicity cone of the elementary symmetric polynomial is a convex relaxation of the set of eigenvalues of matrices in k-PSD closure (ii) Observing a connection between matrices in the k-PSD closure and matrices satisfying the restricted isometry property (RIP).
Video:
Slides:
Seminar: David de Laat (TU Delft)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-david-de-laat-tu-delft
- Seminar: David de Laat (TU Delft)
- 2021-01-28T16:00:00+01:00
- 2021-01-28T17:00:00+01:00
- When Jan 28, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Add event to calendar iCal
Speaker: David de Laat (TU Delft)
Title: Sphere packing and semidefinite programming
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
compute bounds in discrete geometry. First I will focus on compact problems
such as the spherical code problem, which asks for the largest number of
points on a unit sphere such that the inner product between any pair of
disctinct points is at most some given constant. Then I will discuss the
(noncompact) sphere packing problem, explain how this connects to problems
in analytic number theory and the conformal bootstrap program, and discuss
how semidefinite programming can be used to obtain improved bounds.
Video:
Slides:
Kick-off seminar: Laura Sanita (TU Eindhoven)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/kick-off-seminar-laura-sanita-tu-eindhoven
- Kick-off seminar: Laura Sanita (TU Eindhoven)
- 2020-12-16T16:00:00+01:00
- 2020-12-16T17:00:00+01:00
- Laura Sanita (TU Eindhoven) will kick-off the Dutch Seminar on Optimization.
- When Dec 16, 2020 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Where Zoom link in the details
- Contact Name Nikhil Bansal
- Web Visit external website
- Add event to calendar iCal
Speaker: Laura Sanita (TU Eindhoven)
Title: On the diameter and the circuit-diameter of polytopes
Zoom link:
Click here to join the zoom meeting.
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
between a pair of vertices of P, when one is allowed to walk on the
edges (1-dimensional faces) of P. Despite decades of studies, it is
still not known whether the diameter of a d-dimensional polytope with n
facets can be bounded by a polynomial function of n and d. This is a
fundamental open question in discrete mathematics, motivated by the
(still unknown) existence of a polynomial pivot rule for the Simplex
method for solving Linear Programs.
A generalized notion of diameter, recently introduced in the
literature, is that of circuit-diameter, defined as the maximum length
of a shortest path between two vertices of P, where the path can use
all edge directions (called circuits) that can arise by translating
some of the facets of P.
In this talk, I will discuss some algorithmic and complexity results
related to the diameter and the circuit-diameter of polytopes,
highlighting important open questions.
Video:
Slides: Slides Laura Sanita