The ring loading problem emerged in the 1990s to model an important special case of telecommunication networks (synchronous optical network rings) which gained attention from practitioners and theorists alike. Given an undirected cycle on $n$ nodes together with nonnegative demands between any pair of nodes, the ring loading problem asks for an unsplittable routing of the demands such that the maximum cumulated demand on any edge is minimized. Let $L$ be the value of such a solution. In the relaxed version of the problem, each demand can be split into two parts where the first part is routed clockwise while the second part is routed counterclockwise. Denote with $L^*$ the maximum load of a minimum split routing solution. In a landmark paper, Schrijver, Seymour, and Winkler [ SIAM J. Discrete Math., 11 (1998), pp. 1--14] showed that $L \leq L^* + \frac{3}{2}D$, where $D$ is the maximum demand value. They also found (implicitly) an instance of the ring loading problem with $L = L^* + \frac{101}{100}D$. Recently, Skutella [ SIAM J. Discrete Math., 30 (2016), pp. 327--342] improved these bounds by showing that $L \leq L^* + \frac{19}{14}D$, and there exists an instance with $L = L^* + \frac{11}{10}D$. We contribute to this line of research by showing that $L \leq L^* + \frac{13}{10}D$. We also take a first step toward lower and upper bounds for small instances.

Compression and sparsification algorithms are frequently applied in a preprocessing step before analyzing or optimizing large networks/graphs. In this paper we propose and study a new framework contracting edges of a graph (merging vertices into supervertices) with the goal of preserving pairwise distances as accurately as possible. Formally, given an edge-weighted graph, the contraction should guarantee that for any two vertices at distance $d$, the corresponding supervertices remain at distance at least $\varphi(d)$ in the contracted graph, where $\varphi$ is a tolerance function bounding the permitted distance distortion. We present a comprehensive picture of the algorithmic complexity of the contraction problem for affine tolerance functions $\varphi(x)=x/\alpha-\beta$, where $\alpha\geq 1$ and $\beta\geq 0$ are arbitrary real-valued parameters. Specifically, we present polynomial-time algorithms for trees as well as hardness and inapproximability results for different graph classes, precisely separating easy and hard cases. Further we analyze the asymptotic behavior of contractions, and find efficient algorithms to compute (nonoptimal) contractions despite our hardness results.

Compression and sparsification algorithms are frequently applied in a preprocessing step before analyzing or optimizing large networks/graphs. \nIn this paper we propose and study a new framework contracting edges of a graph (merging vertices into super-vertices) with the goal of preserving pairwise distances as accurately as possible. \nFormally, given an edge-weighted graph, the contraction should guarantee that for any two vertices at distance d, the corresponding super-vertices remain at distance at least \\varphi(d) in the contracted graph, where \\varphi is a tolerance function bounding the permitted distance distortion. \nWe present a comprehensive picture of the algorithmic complexity of the contraction problem for affine tolerance functions \\varphi(x)=x/\\alpha-\\beta, where \\alpha \\geq 1 and \\beta \\geq 0 are arbitrary real-valued parameters. \nSpecifically, we present polynomial-time algorithms for trees as well as hardness and inapproximability results for different graph classes, precisely separating easy and hard cases. \nFurther we analyze the asymptotic behavior of the size of contractions, and find efficient algorithms to compute (non-optimal) contractions despite our hardness results.