In the Submodular Facility Location problem (SFL) we are given a collection of $n$ clients and $m$ facilities in a metric space. A feasible solution consists of an assignment of each client to some facility. For each client, one has to pay the distance to the associated facility. Furthermore, for each facility $f$ to which we assign the subset of clients $S^f$, one has to pay the opening cost $g(S^f)$, where $g(\cdot)$ is a monotone submodular function with $g(\emptyset)=0$. SFL is APX-hard since it includes the classical (metric uncapacitated) Facility Location problem (with uniform facility costs) as a special case. Svitkina and Tardos [SODA'06] gave the current-best $O(\log n)$ approximation algorithm for SFL. The same authors pose the open problem whether SFL admits a constant approximation and provide such an approximation for a very restricted special case of the problem. We make some progress towards the solution of the above open problem by presenting an $O(\log\log n)$ approximation. Our approach is rather flexible and can be easily extended to generalizations and variants of SFL. In more detail, we achieve the same approximation factor for the practically relevant generalizations of SFL where the opening cost of each facility $f$ is of the form $p_f+g(S^f)$ or $w_f\cdot g(S^f)$, where $p_f,w_f \geq 0$ are input values. We also obtain an improved approximation algorithm for the related Universal Stochastic Facility Location problem. In this problem one is given a classical (metric) facility location instance and has to a priori assign each client to some facility. Then a subset of active clients is sampled from some given distribution, and one has to pay (a posteriori) only the connection and opening costs induced by the active clients. The expected opening cost of each facility $f$ can be modelled with a submodular function of the set of clients assigned to $f$.

The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph G. Our goal is to find a subgraph S of G with the minimum number of edges which is 2-vertex-connected, namely S remains connected after the deletion of an arbitrary node. 2VCSS is well-studied in terms of approximation algorithms, and the current best (polynomial-time) approximation factor is 10/7 by Heeger and Vygen [SIDMA'17] (improving on earlier results by Khuller and Vishkin [STOC'92] and Garg, Vempala and Singla [SODA'93]). Here we present an improved 4/3 approximation. Our main technical ingredient is an approximation preserving reduction to a conveniently structured subset of instances which are "almost" 3-vertex-connected. The latter reduction might be helpful in future work.

The complexity of computing the flip distance between two triangulations of a simple convex polygon is unknown. Here we approach the problem from a parameterized complexity perspective and improve upon the 2k kernel of Lucas [12]. Specifically, we describe a kernel of size 4k3 and then show how it can be improved to (1+ϵ)k for every constant ϵ>0. By ensuring that the kernel consists of a single instance our result yields a kernel of the same magnitude (up to additive terms) for the almost equivalent rotation distance problem on rooted, ordered binary trees. The earlier work of Lucas left the kernel as a disjoint set of instances, potentially allowing very minor differences in the definition of the size of instances to accumulate, causing a constant-factor distortion in the kernel size when switching between flip distance and rotation distance formulations. Our approach avoids this sensitivity. We have also undertaken experiments to understand how much reduction is achieved by our kernel in practice.