29.04.2025 16:00 Leander Schnaars: A 3.415-Approximation for Coflow Scheduling via Iterated Rounding
We provide an algorithm giving a 140/41 (3.415)-approximation for Coflow Scheduling and a 4.36-approximation for Coflow Scheduling with release dates. This improves upon the best known 4- and respectively 5-approximations and addresses an open question posed by Agarwal, Rajakrishnan, Narayan, Agarwal, Shmoys, and Vahdat [Aga+18], Fukunaga [Fuk22], and others. We additionally show that in an asymptotic setting, the algorithm achieves a (2+ϵ)-approximation, which is essentially optimal under P≠NP. The improvements are achieved using a novel edge allocation scheme using iterated LP rounding together with a framework which enables establishing strong bounds for combinations of several edge allocation algorithms.
Source
05.05.2025 16:30 Michiel Renger: TBA
TBA
Source
06.05.2025 16:00 Alexandra Lassota: Integer Programs meet Fixed-Parameter Tractability
Solving Integer Programs (IPs) is generally NP-hard. But this does not imply that all instances are inherently hard.
In fact, a substantial body of research has focused on identifying tractable subclasses and developing efficient (fixed-parameter tractable) time algorithms for those.
This talk will give a little overview of some of the key results and techniques.
Source
14.05.2025 12:15 Luciana Dalla Valle (University of Torino, IT): Approximate Bayesian conditional copulas
According to Sklar’s theorem, any multidimensional absolutely continuous distribution function can be uniquely represented as a copula, which captures the dependence structure among the vector components. In real data applications, the interest of the analyses often lies on specific functionals of the dependence, which quantify aspects of it in a few numerical values. A broad literature exists on such functionals, however extensions to include covariates are still limited. This is mainly due to the lack of unbiased estimators of the conditional copula, especially when one does not have enough information to select the copula model. Several Bayesian methods to approximate the posterior distribution of functionals of the dependence varying according covariates are presented and compared; the main advantage of the investigated methods is that they use nonparametric models, avoiding the selection of the copula, which is usually a delicate aspect of copula modelling. These methods are compared in simulation studies and in two realistic applications, from civil engineering and astrophysics.
Source