DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.11

Pinning on Tight Cuts: Improved Algorithm and Bounds for Unsplittable Multicommodity Flows in Outerplanar Graphs

Authors: David Alemán Espinosa and Niklas Schlomberg

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

The multicommodity flow problem in an undirected capacitated graph G is specified by a set of source-sink pairs with nonnegative demands. A flow is feasible if it routes all demands without exceeding the edge capacities, and it is unsplittable if it routes each demand along a single path. Let α be the smallest value such that the existence of a feasible flow implies the existence of an unsplittable flow that exceeds the edge capacities by at most + α d_max. Schrijver, Seymour, and Winkler showed that α ∈ [1.01, 1.5] if G is a cycle. These bounds were ultimately improved to α ∈ [1.1, 1.3] by Skutella and Däubel. Recently, Alemán Espinosa and Kumar extended this constant upper bound to the broader class of outerplanar graphs, and showed that if G is outerplanar then α ≤ 3.6. We show that α ∈ [4/3,2] if G is outerplanar. We introduce a novel technique that considers the global parameters of the instance, and that may be useful in other (more general) settings where the cut-condition is sufficient, or nearly sufficient, for the existence of a feasible flow.

Cite as

David Alemán Espinosa and Niklas Schlomberg. Pinning on Tight Cuts: Improved Algorithm and Bounds for Unsplittable Multicommodity Flows in Outerplanar Graphs. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alemanespinosa_et_al:LIPIcs.ICALP.2026.11,
  author =	{Alem\'{a}n Espinosa, David and Schlomberg, Niklas},
  title =	{{Pinning on Tight Cuts: Improved Algorithm and Bounds for Unsplittable Multicommodity Flows in Outerplanar Graphs}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.11},
  URN =		{urn:nbn:de:0030-drops-264008},
  doi =		{10.4230/LIPIcs.ICALP.2026.11},
  annote =	{Keywords: Unsplittable Flows, Multicommodity Flows, Planar Graphs}
}

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.29

Approximation Algorithms for Correlated Knapsack Orienteering

Authors: David Alemán Espinosa and Chaitanya Swamy

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract

We consider the correlated knapsack orienteering (CorrKO) problem: we are given a travel budget B, processing-time budget W, finite metric space (V,d) with root ρ ∈ V, where each vertex is associated with a job with possibly correlated random size and random reward that become known only when the job completes. Random variables are independent across different vertices. The goal is to compute a ρ-rooted path of length at most B, in a possibly adaptive fashion, that maximizes the reward collected from jobs that processed by time W. To our knowledge, CorrKO has not been considered before, though prior work has considered the uncorrelated problem, stochastic knapsack orienteering, and correlated orienteering, which features only one budget constraint on the sum of travel-time and processing-times. Gupta et al. [Gupta et al., 2015] showed that the uncorrelated version of this problem has a constant-factor adaptivity gap. We show that, perhaps surprisingly and in stark contrast to the uncorrelated problem, the adaptivity gap of CorrKO is is at least Ω(max{√log(B),√(log log(W))}). Complementing this result, we devise non-adaptive algorithms that obtain: (a) O(log log W)-approximation in quasi-polytime; and (b) O(log W)-approximation in polytime. This also establishes that the adaptivity gap for CorrKO is at most O(log log W). We obtain similar guarantees for CorrKO with cancellations, wherein a job can be cancelled before its completion time, foregoing its reward. We show that an α-approximation for CorrKO implies an O(α)-approximation for CorrKO with cancellations. We also consider the special case of CorrKO where job sizes are weighted Bernoulli distributions, and more generally where the distributions are supported on at most two points (2CorrKO). Although weighted Bernoulli distributions suffice to yield an Ω(√{log log B}) adaptivity-gap lower bound for (uncorrelated) stochastic orienteering, we show that they are easy instances for CorrKO. We develop non-adaptive algorithms that achieve O(1)-approximation, in polytime for weighted Bernoulli distributions, and in (n+log B)^O(log W)-time for 2CorrKO. (Thus, our adaptivity-gap lower-bound example, which uses distributions of support-size 3, is tight in terms of support-size of the distributions.) Finally, we leverage our techniques to provide a quasi-polynomial time O(log log B) approximation algorithm for correlated orienteering improving upon the approximation guarantee in [Bansal and Nagarajan, 2015].

Cite as

David Alemán Espinosa and Chaitanya Swamy. Approximation Algorithms for Correlated Knapsack Orienteering. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 29:1-29:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{alemanespinosa_et_al:LIPIcs.APPROX/RANDOM.2024.29,
  author =	{Alem\'{a}n Espinosa, David and Swamy, Chaitanya},
  title =	{{Approximation Algorithms for Correlated Knapsack Orienteering}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{29:1--29:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.29},
  URN =		{urn:nbn:de:0030-drops-210224},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.29},
  annote =	{Keywords: Approximation algorithms, Stochastic orienteering, Adaptivity gap, Vehicle routing problems, LP rounding algorithms}
}

Search Results

Documents authored by Alemán Espinosa, David

Pinning on Tight Cuts: Improved Algorithm and Bounds for Unsplittable Multicommodity Flows in Outerplanar Graphs

Abstract

Cite as

Approximation Algorithms for Correlated Knapsack Orienteering

Abstract

Cite as

Thanks for your feedback!

Could not send message