Events

Events folder

Seminar: Jasper van Doornmalen (TU Eindhoven) + Daniel Brosch (Tilburg University), 2 PhD talks

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

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:

Real-life project or machine scheduling involves: (i) limited information about the exact task durations, and (ii) an opportunity to reschedule each time a task completed its processing and a machine becomes idle. Robust optimization is the natural methodology to cope with the first characteristic, yet the existing literature does not consider the possibility to adjust decisions as more information about the tasks' durations is revealed. This is despite that re-optimizing the schedule is a standard practice.

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

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

Let Substr_k(T) denote the set of length-k substrings of a given string T for a given integer k>0. We study the following basic string problem, called Shortest equivalent string: Given a set S_k of n length-k strings and an integer z>0, find a shortest string T such that Substr_k(T)=S_k. The Shortest equivalent string problem arises naturally as an encoding problem in many real-world applications; e.g., in data privacy, in data compression, and in bioinformatics. We answer this problem by showing that it is equivalent to finding a shortest walk that crosses every edge of a graph, and we give an algorithm for the latter problem.
 

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

We establish a broad methodological foundation for mixed-integer optimization with learned constraints. We propose an end-to-end pipeline for data-driven decision making in which constraints and objectives are directly learned from data using machine learning, and the trained models are embedded in an optimization formulation. We exploit the mixed-integer optimization-representability of many machine learning methods, including linear models, decision trees, ensembles, and multi-layer perceptrons. The consideration of multiple methods allows us to capture various underlying relationships between decisions, contextual variables, and outcomes. We also characterize a decision trust region using the convex hull of the observations, to ensure credible recommendations and avoid extrapolation. We efficiently incorporate this representation using column generation and clustering. In combination with domain-driven constraints and objective terms, the embedded models and trust region define a mixed-integer optimization problem for prescription generation. We implement this framework as a Python package (OptiCL) for practitioners. We demonstrate the method in both chemotherapy optimization and World Food Programme planning. The case studies illustrate the benefit of the framework in generating high-quality prescriptions, the value added by the trust region, the incorporation of multiple machine learning methods, and the inclusion of multiple learned constraints.

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

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

Integer programming is a very versatile discrete optimisation problem with many applications in science and engineering. From the viewpoint of algorithms and complexity, it is an active area of research that offers interesting and visible open problems.  In this talk, I will survey some recent results on the complexity of integer programming. These include the general integer programming problem in standard form with small coefficients. Here field of parameterised complexity has developed tools to provide lower bounds on the complexity of IP based on the exponential time hypothesis (ETH). The goal of this talk is to give an overview on recent progress and open problems in this area.


Video:

Slides: 
Slides

Seminar: Lightning Talks (several speakers), 2022-1

  • When Feb 10, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
  • Add event to calendar iCal

Speaker: Several speakers (hopefully 12-15)

Title: Lightning Talks

Our first lightning talk was very successful, so we will now have 2 per year, in between the first two regular seminars of each semester. 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 sign up here with your name and the subject of your talk (can be TBD) by *Friday February 4th*:

https://docs.google.com/spreadsheets/d/1KH6_dL7yz4I5cXH8udlXAyZrbTwUAjEgQLoslxt-yz4/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: 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)

Zoom link: 

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:

Slides: 
Slides

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

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

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

Video of the talk of Hadi Abbaszadehpeivasti:



Slides of the talk of Hadi Abbaszadehpeivasti:  

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.

Zoom link: 

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

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

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.
Arxiv link: https://arxiv.org/abs/2011.04027

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

Zoom link: 

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

Zoom link: 

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

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

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

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: 

Slides (pdf)
Slides (pptx)

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: 

Notes left side: https://scribbletogether.com/whiteboard/61430EF3-FF39-4376-BB52-42EC7210A1B2
Notes right side: https://scribbletogether.com/whiteboard/F396C9B4-8728-4CB4-A44B-BF3F2E2BB93E
Polytopes: https://polytopes.huiberts.me/cube/list
Nice twitter abstract: https://twitter.com/SophieHuiberts/status/1397950845531017217

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

Zoom link: 

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:

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

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

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:

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

Zoom link: 

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

Zoom link: 

Click here to join the zoom meeting.
(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

Slides_Laura_Sanita_16-12-2020_DutchSeminarOnOptimization.pdf

Read More…

DavidDeLaat_28-01-2021_DutchSeminarOnOptimization_Slides.pdf

Read More…