Submodular unsplittable flow on trees

Anna Adamaszek, Parinya Chalermsook, Alina Ene, Andreas Wiese

Abstract

We study the Unsplittable Flow problem ($\mathsf{UFP}$) on trees with a submodular objective function. The input is a tree with edge capacities and a collection of tasks, each defined by a source-sink pair and a demand. A subset of tasks is feasible if their demands can be routed simultaneously without violating edge capacities. Our goal is to select a feasible subset that maximizes a submodular objective function. We present an $O(k \log n)$-approximation algorithm, where $k$ is the pathwidth of the tree. Since any tree has pathwidth $O(\log n)$, this yields an $O(\log^2 n)$ approximation for arbitrary trees, matching the best known ratio for the linear objective case. Our approach relies on a new geometric relaxation and the contention resolution framework. Additionally, we provide a QPTAS for upward instances and prove APX-hardness for arbitrary upward instances.

Introduction

The Unsplittable Flow Problem (UFP) is a cornerstone of network optimization, representing scenarios where requests must be fulfilled in their entirety or not at all. While UFP on paths has seen significant progress, tree topologies present unique structural challenges. Furthermore, most existing literature focuses on linear objectives where the total profit is the sum of individual task profits. This paper extends the state-of-the-art to submodular objective functions, which more accurately model real-world scenarios involving diminishing returns.

Methodology

The core of our contribution is a robust algorithmic framework built on three pillars:

1. Geometric Linear Programming Relaxation

Building on recent work for UFP on paths (Bonsma et al., 2014; Anagnostopoulos et al., 2014), we develop a novel geometric relaxation for trees. By visualizing tasks as rectangles in a 2D space constrained by edge capacities, we create a "staircase" structure. This geometric perspective provides a tighter bound than traditional flow-based relaxations, which often suffer from large integrality gaps in tree networks.

2. Pathwidth Decomposition

The complexity of routing on a tree can be characterized by its pathwidth ($k$). We decompose the tree into a set of paths and demonstrate that any task interaction can be restricted to $O(k)$ paths. This decomposition allows us to leverage path-based techniques while maintaining global feasibility across the tree structure.

3. Contention Resolution Framework

To handle the submodular objective, we integrate our geometric relaxation with the contention resolution (CR) schemes of Chekuri et al. (2009). The structured nature of our LP relaxation ensures that fractional solutions can be rounded into feasible integral sets with provable approximation guarantees.

Results

Our primary result is the first non-trivial approximation guarantee for Submodular UFP on trees:

  • General Trees: We achieve an $O(k \log n)$ approximation, which simplifies to $O(\log^2 n)$ for any tree with $n$ nodes. This matches the current best-known results for the linear objective case.
  • Specialized Topologies: For trees with constant pathwidth, such as caterpillars or spiders, the approximation ratio improves to $O(\log n)$.
  • Upward Instances: For instances where the source is a descendant of the sink, we provide a Quasi-Polynomial Time Approximation Scheme (QPTAS), assuming quasi-polynomially bounded input data.
  • Hardness Results: We prove that upward instances on trees are APX-hard when input data is arbitrary, contrasting with the path setting where better approximations are possible.

Conclusion

This research provides a unified approach to Submodular UFP on trees, bridging the gap between linear and submodular optimization in complex network topologies. The geometric relaxation introduced here is robust and extends to related problems like the Storage Allocation Problem and UFP with bag constraints. Future work may focus on closing the gap between the $O(\log^2 n)$ ratio and the constant-factor approximations available for simpler path graphs.

Summary updated

Abstract

We study the Unsplittable Flow problem ( $$\mathsf {UFP}$$ UFP ) on trees with a submodular objective function. The input to this problem is a tree with edge capacities and a collection of tasks, each characterized by a source node, a sink node, and a demand. A subset of the tasks is feasible if the tasks can simultaneously send their demands from the source to the sink without violating the edge capacities. The goal is to select a feasible subset of the tasks that maximizes a submodular objective function. Our main result is an $$O(k\log n)$$ O ( k log n ) -approximation algorithm for Submodular UFP on trees where k denotes the pathwidth of the given tree. Since every tree has pathwidth $$O(\log n)$$ O ( log n ) , we obtain an $$O(\log ^2 n)$$ O ( log 2 n ) approximation for arbitrary trees. This is the first non-trivial approximation guarantee for the problem, matching the best known approximation ratio for UFP on trees with a linear objective function. Our main technical contribution is a new geometric relaxation for UFP on trees that builds on the recent work of Bonsma et al. (2014, FOCS), Anagnostopoulos et al. (Amazing 2+ $$\epsilon $$ ϵ approximation for unsplittable flow on a path, SIAM, pp 26–41, 2014) for UFP on paths with a linear objective. Our relaxation is very structured, so it can be combined with the contention resolution framework of Chekuri et al. (2009, STOC). Our approach is robust and extends to several related problems, such as UFP with bag constraints and the Storage Allocation Problem. Additionally, we study the special case of UFP on trees with a linear objective and upward instances where, for each task, the source node is a descendant of the sink node. Such instances generalize UFP on paths. We build on the work of Bansal et al. (A quasi-PTAS for unsplittable flow on line graphs, ACM, pp 721–729, 2006) for UFP on paths and obtain a QPTAS for upward instances when the input data is quasi-polynomially bounded. We complement this result by showing that, unlike the path setting, upward instances are $$\mathsf {APX}$$ APX -hard if the input data is arbitrary.
BibTeX
@inproceedings{adamaszek2016submodular,
  author = {Anna Adamaszek and Parinya Chalermsook and Alina Ene and Andreas Wiese},
  title = {{Submodular unsplittable flow on trees}},
  booktitle = {IPCO},
  year = {2016},
  doi = {10.1007/978-3-319-33461-5\_28},
}

Loading related content...

Figure