Flow time is one of the most natural metrics to optimize in scheduling, but algorithmically it can be notoriously difficult to handle. I will talk about some recent advances in this topic, focusing on two results by myself and co-authors: a PTAS for the sum of weighted flow times on a single machine and improved approximation guarantees for parallel unrelated machines. The first result is enabled by a study of structural properties of constraints in a natural ILP formulation and the second result relies on a novel connection to discrepancy theory.

1. Jesse van Rhijn (Twente)
2. Luis Vargas (CWI)
3. Michelle Sweering (CWI)
4. Jack Mayo (UvA)
5. Celine Swennenhuis (TU/e)
6. Sukanya Pandey (Utrecht)
7. Yanlin Chen (CWI)
8. Moslem Zamani (Tilburg)
9. Christopher Hojny (TU/e)
10. Till Miltzow (Utrecht)
11. Emir Demirović (TU Delft)
12. Solon Pissis (CWI)

Integer semidefinite programming can be viewed as a generalization of integer programming where the vector variables are replaced by positive semidefinite integer matrix variables. The combination of positive semidefiniteness and integrality allows to formulate various optimization problems as integer semidefinite programs (ISDPs). Nevertheless, ISDPs have received attention only very recently.
In this talk we show how to extend the Chvàtal-Gomory (CG) cutting-plane procedure to ISDPs. We also show how to exploit CG cuts in a branch-and-cut framework for ISDPs. Finally, we demonstrate the practical strength of the CG cuts in our branch-and-cut algorithm. Our results provide a new perspective on ISDPs.
This is joint work with F. de Meijer

Determining if a graph has an independent set of size \(k\) is a well known NP-hard problem. Clearly counting the number of independent sets of size \(k\) is at least as hard. More surprisingly perhaps is that determining the number of all independent sets is just as hard, even for graphs of maximum degree \(3\). In this talk I will survey some recent results about the hardness of *approximately* determining the number of independent sets and more generally of other evaluations of the generating function of the independent sets in a graph, also known as the independence polynomial. The location of the complex zeros of the independence polynomial play an important role.

A key problem in mathematical imaging, signal processing and computational statistics is the minimization of non-convex objective functions over conic domains, which are continuous but potentially non-smooth at the boundary of the feasible set. For such problems, this paper proposes a new family of first and second-order interior-point methods for non-convex and non-smooth conic constrained optimization problems, combining the Hessian-barrier method with quadratic and cubic regularization techniques. Our approach is based on a potential-reduction mechanism and attains a suitably defined class of approximate first- or second-order KKT points with worst-case iteration complexity \(O(\epsilon^{-2})\) (first-order) and \(O(\epsilon^{-3/2})\) (second-order), respectively. Based on these findings, we develop a new double loop path-following scheme attaining the same complexity, modulo adjusting constants. These complexity bounds are known to be optimal in the unconstrained case, and our work shows that they are upper bounds in the case with complicated constraints as well. A key feature of our methodology is the use of self-concordant barriers to construct strictly feasible iterates via a disciplined decomposition approach and without sacrificing on the iteration complexity of the method. To the best of our knowledge, this work is the first which achieves these worst-case complexity bounds under such weak conditions for general conic constrained optimization problems.
This is joint work with Pavel Dvurechensky (WIAS Berlin) and based on the paper: https://arxiv.org/abs/2111.00100

We consider extensions of the Shannon relative entropy, referred to as \(f\)-divergences. Three classical related computational problems are typically associated with these divergences: (a) estimation from moments, (b) computing normalizing integrals, and (c) variational inference in probabilistic models. These problems are related to one another through convex duality, and for all them, there are many applications throughout data science, and we aim for computationally tractable approximation algorithms that preserve properties of the original problem such as potential convexity or monotonicity. In order to achieve this, we derive a sequence of convex relaxations for computing these divergences from non-centered covariance matrices associated with a given feature vector: starting from the typically non-tractable optimal lower-bound, we consider an additional relaxation based on ``sums-of-squares'', which is is now computable in polynomial time as a semidefinite program, as well as further computationally more efficient relaxations based on spectral information divergences from quantum information theory (see https://arxiv.org/abs/2206.13285 for details).