A note on two source location problems

We consider Source Location ($\mathsf{SL}$) problems: given a capacitated network $G=(V,E)$, cost $c(v)$ and a demand $d(v)$ for every $v\in V$, choose a min-cost $S\subseteq V$ so that $\lambda (v,S)⩾d(v)$ holds for every $v\in V$, where $\lambda (v,S)$ is the maximum flow value from v to S. In the directed variant, we have demands $d^{\mathit{in}}(v)$ and $d^{\mathit{out}}(v)$ and we require $\lambda (S,v)⩾d^{\mathit{in}}(v)$ and $\lambda (v,S)⩾d^{\mathit{out}}(v)$. Undirected $\mathsf{SL}$ is (weakly) NP-hard on stars with $r(v)=0$ for all v except the center. But, it is known to be polynomially solvable for uniform costs and uniform demands. For general instances, both directed an undirected $\mathsf{SL}$ admit a $(\ln D+1)$-approximation algorithms, where D is the sum of the demands; up to constant this is tight, unless P = NP. We give a pseudopolynomial algorithm for undirected $\mathsf{SL}$ on trees with running time $O(|V|{\Delta }^3)$, where $\Delta ={\max }_{v\in V}d(v)$. This algorithm is used to derive a linear time algorithm for undirected $\mathsf{SL}$ with $\Delta ⩽3$. We also consider the Single Assignment Source Location ($\mathsf{SASL}$) where every $v\in V$ should be assigned to a single node $s(v)\in S$. While the undirected $\mathsf{SASL}$ is in P, we give a $(\ln |V|+1)$-approximation algorithm for the directed case, and show that this is tight, unless P = NP.     

The Ramsey property for Banach spaces and Choquet simplices,and applications

We show that the class of finite-dimensional Banach spaces and the class of finite-dimensional Choquet simplices have the Ramsey property. As an application, we show that the group $\mathrm{Aut}(\mathbb{G})$ of surjective linear isometries of the Gurarij space $\mathbb{G}$ is extremely amenable, and that the canonical action $\mathrm{Aut}(\mathbb{P})?\mathbb{P}$ is the universal minimal flow of the group $\mathrm{Aut}(\mathbb{P})$ of affine homeomorphisms of the Poulsen simplex $\mathbb{P}$. This answers questions of Melleray–Tsankov and Conley–Törnquist.     

Breaking points in centralizer lattices

In this note, we prove that the centralizer lattice $\mathfrak{C}(G)$ of a group G cannot be written as a union of two proper intervals. In particular, it follows that $\mathfrak{C}(G)$ has no breaking point. As an application, we show that the generalized quaternion 2-groups are not capable.