DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.74

Unsplittable Transshipments

Authors: Srinwanti Debgupta, Sarah Morell, and Martin Skutella

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

Abstract

We introduce the Unsplittable Transshipment Problem in directed graphs with multiple sources and sinks. An unsplittable transshipment routes given supplies and demands using at most one path for each source-sink pair. Although they are a natural generalization of single source unsplittable flows, unsplittable transshipments raise interesting new challenges and require novel algorithmic techniques. As our main contribution, we give a nontrivial generalization of a seminal result of Dinitz, Garg, and Goemans (1999) by showing how to efficiently turn a given transshipment x into an unsplittable transshipment y with y_a < x_a+d_max for all arcs a, where d_max is the maximum demand (or supply) value. Further results include bounds on the number of rounds required to satisfy all demands, where each round consists of an unsplittable transshipment that routes a subset of the demands while respecting arc capacity constraints.

Cite as

Srinwanti Debgupta, Sarah Morell, and Martin Skutella. Unsplittable Transshipments. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 74:1-74:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{debgupta_et_al:LIPIcs.ICALP.2026.74,
  author =	{Debgupta, Srinwanti and Morell, Sarah and Skutella, Martin},
  title =	{{Unsplittable Transshipments}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{74:1--74:17},
  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.74},
  URN =		{urn:nbn:de:0030-drops-264634},
  doi =		{10.4230/LIPIcs.ICALP.2026.74},
  annote =	{Keywords: Network flow, unsplittable flow, flow augmentation}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2018.33

Diversity Maximization in Doubling Metrics

Authors: Alfonso Cevallos, Friedrich Eisenbrand, and Sarah Morell

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract

Diversity maximization is an important geometric optimization problem with many applications in recommender systems, machine learning or search engines among others. A typical diversification problem is as follows: Given a finite metric space (X,d) and a parameter k in N, find a subset of k elements of X that has maximum diversity. There are many functions that measure diversity. One of the most popular measures, called remote-clique, is the sum of the pairwise distances of the chosen elements. In this paper, we present novel results on three widely used diversity measures: Remote-clique, remote-star and remote-bipartition. Our main result are polynomial time approximation schemes for these three diversification problems under the assumption that the metric space is doubling. This setting has been discussed in the recent literature. The existence of such a PTAS however was left open. Our results also hold in the setting where the distances are raised to a fixed power q >= 1, giving rise to more variants of diversity functions, similar in spirit to the variations of clustering problems depending on the power applied to the pairwise distances. Finally, we provide a proof of NP-hardness for remote-clique with squared distances in doubling metric spaces.

Cite as

Alfonso Cevallos, Friedrich Eisenbrand, and Sarah Morell. Diversity Maximization in Doubling Metrics. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 33:1-33:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cevallos_et_al:LIPIcs.ISAAC.2018.33,
  author =	{Cevallos, Alfonso and Eisenbrand, Friedrich and Morell, Sarah},
  title =	{{Diversity Maximization in Doubling Metrics}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{33:1--33:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.33},
  URN =		{urn:nbn:de:0030-drops-99818},
  doi =		{10.4230/LIPIcs.ISAAC.2018.33},
  annote =	{Keywords: Remote-clique, remote-star, remote-bipartition, doubling dimension, grid rounding, epsilon-nets, polynomial time approximation scheme, facility location, information retrieval}
}

Search Results

Documents authored by Morell, Sarah

Unsplittable Transshipments

Abstract

Cite as

Diversity Maximization in Doubling Metrics

Abstract

Cite as

Thanks for your feedback!

Could not send message