# Events

Events folder

## Seminar: Andreas Wiese (Vrije Universiteit Amsterdam)

• 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)

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

Abstract:

In the Unsplittable Flow on a Path problem (UFP) we are given a path with edge capacities, and a set of tasks where each task is characterized by a subpath, a demand, and a weight. The goal is to select a subset of tasks of maximum total weight such that the total demand of the selected tasks using each edge $e$ is at most the capacity of $e$. The problem admits a QPTAS. After a long sequence of improvements, the currently best known polynomial time approximation algorithm for UFP has an approximation ratio of $1+\frac{1}{e+1}+\eps < 1.269$. It has been an open question whether this problem admits a PTAS.
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

• When Dec 09, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
• Add event to calendar iCal

Title:

Utku Karaca : Differentially Private Resource Sharing

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

Difference-of-convex (DC) problems arise naturally in many applications. The DCA (Difference-of-Convex Algorithm) is a popular algorithm for tackling DC problems. In this talk, we study the convergence rate of the DCA, also known as the convex-concave procedure, by using Performance estimation. We derive a worst-case convergence rate of O(1/sqrt(N)) after N iterations of the objective gradient norm for certain classes of unconstrained DC problems. We give an example which shows the order of convergence cannot be improved for a certain class of DC functions. In addition, we study DC problems on a given convex set and we obtain a convergence rate O(1/N) for some termination criterion. Finally, we investigate the DCA with regularization and we get the same convergence rate.

https://arxiv.org/abs/2109.13566

Slides

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

Slides

## Seminar: Britta Peis (RWTH Aachen University), International speaker

• 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.

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

Abstract:

We present a general approximation framework for weighted integer covering problems. In a weighted integer covering problem, the goal is to determine a non-negative integer solution x to  system Ax ≥ r minimizing a non-negative linear cost function c. We analyze the performance of two commonly used primal-dual algorithms (greedy dual and dual fitting) on some restricted systems (A, r) that we call greedy systems. We also study the impact of truncation, i.e. a scheme for improving the IP formulation of the problem. (Joint work with Jose Verschae, Niklas Rieken, and Andreas Wierz.)

Video
:

Slides

Slides

## Seminar: Lucas Slot (CWI) + Juan José Maulén (Groningen), 2 PhD talks

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

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):

The classical Positvestellensaetze of Putinar and Schmuedgen state that the positivity of a polynomial f over a (compact) semialgebraic set S can be verified by expanding f as a conic combination of the polynomials that define S, using sums of squares of polynomials as coefficients. Recently, there has been an interest in proving bounds on the largest degree of the sum-of-squares coefficients involved in this expansion. Such bounds have direct implications for the convergence rate of Lasserre-type hierarchies for polynomial optimization. We present the polynomial kernel method for proving degree bounds on special sets S, which was first used in the case of the hypersphere by Fang and Fawzi.
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.

Video of the talk of Lucas Slot:

Slides of the talk of Lucas Slot:

Slides

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

Slides

## Seminar: Martin Skutella (TU Berlin), International speaker

• 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

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

Abstract:

The Quickest Transshipment Problem is to route flow as quickly as possible from sources with supplies to sinks with demands in a network with capacities and transit times on the arcs. It is of fundamental importance for numerous applications in areas such as logistics, production, traffic, evacuation, and finance. More than 25 years ago, Hoppe and Tardos presented the first (strongly) polynomial-time algorithm for this problem. Their approach, as well as subsequently derived algorithms with strongly polynomial running time, are hardly practical as they rely on parametric submodular function minimization via Megiddo's method of parametric search. The main contribution of this paper is a considerably faster algorithm for the Quickest Transshipment Problem that instead employs a subtle extension of the Discrete Newton Method. This improves the previously best known running time of $\tilde{O}(m^4k^{14})$ to $\tilde O(m^2k^5+m^3k^3+m^3n)$, where $n$ is the number of nodes, $m$ the number of arcs, and $k$ the number of sources and sinks. This is joint work with Miriam Schlöter (ETH Zurich) and Khai Van Tran (TU Berlin).

Video
:

Slides

Slides

## Seminar: Samuel Fiorini (Bruxelles), International speaker

• 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

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

Abstract:

We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for k=0 (bipartite graphs) and for k=1. We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to b-matching. This is joint work with Gwenaël Joret (ULB), Stefan Weltge (TUM) and Yelena Yuditsky (ULB).

Video
:

Slides

Slides

## Seminar: Lightning Talks (several speakers)

• 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 :)

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

• 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

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):

In the Bin Packing problem one is given n items with different weights and m bins with a given capacity; the goal is to distribute the items over the bins without exceeding the capacity.

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)

• 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

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

Abstract:

The geometry of the graph of the objective function has a direct
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:

Slides

## Seminar: Moritz Buchem (Maastricht) + Michelle Sweering (CWI)

• 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:

Michelle Sweering: On Breaking k-Trusses

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

We formalize the concept of additive approximation schemes and apply it to load balancing problems on identical machines.
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

Slides

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

Slides

## Seminar: Santanu Dey (Georgia Tech)

• 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

(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:

Slides Santanu Dey

## Seminar: David de Laat (TU Delft)

• 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

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

Abstract:

In this talk I will discuss how semidefinite programming can be used to
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:

Slides David De Laat

## Kick-off seminar: Laura Sanita (TU Eindhoven)

Laura Sanita (TU Eindhoven) will kick-off the Dutch Seminar on Optimization.

Speaker: Laura Sanita (TU Eindhoven)

Title: On the diameter and the circuit-diameter of polytopes

(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract:

The diameter of a polytope P is the maximum length of a shortest path
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