Acceleration for Distributed Transshipment and Parallel Maximum Flow Article Swipe

View

Grunau, Christoph , Kyng, Rasmus , Zuzic, Goran ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2511.06581

We combine several recent advancements to solve $(1+\varepsilon)$-transshipment and $(1+\varepsilon)$-maximum flow with a parallel algorithm with $\tilde{O}(1/\varepsilon)$ depth and $\tilde{O}(m/\varepsilon)$ work. We achieve this by developing and deploying suitable parallel linear cost approximators in conjunction with an accelerated continuous optimization framework known as the box-simplex game by Jambulapati et al. (ICALP 2022). A linear cost approximator is a linear operator that allows us to efficiently estimate the cost of the optimal solution to a given routing problem. Obtaining accelerated $\varepsilon$ dependencies for both problems requires developing a stronger multicommodity cost approximator, one where cancellations between different commodities are disallowed. For maximum flow, we observe that a recent linear cost approximator due to Agarwal et al. (SODA 2024) can be augmented with additional parallel operations and achieve $\varepsilon^{-1}$ dependency via the box-simplex game. For transshipment, we also construct a deterministic and distributed approximator. This yields a deterministic CONGEST algorithm that requires $\tilde{O}(\varepsilon^{-1}(D + \sqrt{n}))$ rounds on general networks of hop diameter $D$ and $\tilde{O}(\varepsilon^{-1}D)$ rounds on minor-free networks to compute a $(1+\varepsilon)$-approximation.

Related Topics

Concepts

Mathematical optimization Computer science Flow network Transshipment (information security) Maximum flow problem Minimum-cost flow problem Acceleration Linear programming Construct (python library) Routing (electronic design automation) Operator (biology) Flow (mathematics) Multi-commodity flow problem Flow routing Algorithm Linear system Distributed computing Dependency (UML) Container (type theory) Decomposition Mathematics Distributed algorithm Scalability

Metadata

Type: preprint
Landing Page: https://doi.org/10.48550/arxiv.2511.06581
OA Status: green
OpenAlex ID: https://openalex.org/W7105165262

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W7105165262

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2511.06581

Digital Object Identifier
Title: Acceleration for Distributed Transshipment and Parallel Maximum Flow

Work title
Type: preprint

OpenAlex work type
Publication year: 2025

Year of publication
Publication date: 2025-11-09

Full publication date if available
Authors: Grunau, Christoph, Kyng, Rasmus, Zuzic, Goran

List of authors in order
Landing page: https://doi.org/10.48550/arxiv.2511.06581

Publisher landing page
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://doi.org/10.48550/arxiv.2511.06581

Direct OA link when available
Concepts: Mathematical optimization, Computer science, Flow network, Transshipment (information security), Maximum flow problem, Minimum-cost flow problem, Acceleration, Linear programming, Construct (python library), Routing (electronic design automation), Operator (biology), Flow (mathematics), Multi-commodity flow problem, Flow routing, Algorithm, Linear system, Distributed computing, Dependency (UML), Container (type theory), Decomposition, Mathematics, Distributed algorithm, Scalability

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex

Full payload

id	https://openalex.org/W7105165262
doi	https://doi.org/10.48550/arxiv.2511.06581
ids.doi	https://doi.org/10.48550/arxiv.2511.06581
ids.openalex	https://openalex.org/W7105165262
fwci
type	preprint
title	Acceleration for Distributed Transshipment and Parallel Maximum Flow
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C126255220
concepts[0].level	1
concepts[0].score	0.6979427933692932
concepts[0].wikidata	https://www.wikidata.org/wiki/Q141495
concepts[0].display_name	Mathematical optimization
concepts[1].id	https://openalex.org/C41008148
concepts[1].level	0
concepts[1].score	0.6140971183776855
concepts[1].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[1].display_name	Computer science
concepts[2].id	https://openalex.org/C114809511
concepts[2].level	2
concepts[2].score	0.5370845198631287
concepts[2].wikidata	https://www.wikidata.org/wiki/Q1412924
concepts[2].display_name	Flow network
concepts[3].id	https://openalex.org/C2776234997
concepts[3].level	2
concepts[3].score	0.5341137051582336
concepts[3].wikidata	https://www.wikidata.org/wiki/Q17134191
concepts[3].display_name	Transshipment (information security)
concepts[4].id	https://openalex.org/C157469704
concepts[4].level	2
concepts[4].score	0.48314398527145386
concepts[4].wikidata	https://www.wikidata.org/wiki/Q2585642
concepts[4].display_name	Maximum flow problem
concepts[5].id	https://openalex.org/C99545648
concepts[5].level	3
concepts[5].score	0.4695435166358948
concepts[5].wikidata	https://www.wikidata.org/wiki/Q2897180
concepts[5].display_name	Minimum-cost flow problem
concepts[6].id	https://openalex.org/C117896860
concepts[6].level	2
concepts[6].score	0.4380490183830261
concepts[6].wikidata	https://www.wikidata.org/wiki/Q11376
concepts[6].display_name	Acceleration
concepts[7].id	https://openalex.org/C41045048
concepts[7].level	2
concepts[7].score	0.42991167306900024
concepts[7].wikidata	https://www.wikidata.org/wiki/Q202843
concepts[7].display_name	Linear programming
concepts[8].id	https://openalex.org/C2780801425
concepts[8].level	2
concepts[8].score	0.42564690113067627
concepts[8].wikidata	https://www.wikidata.org/wiki/Q5164392
concepts[8].display_name	Construct (python library)
concepts[9].id	https://openalex.org/C74172769
concepts[9].level	2
concepts[9].score	0.42303380370140076
concepts[9].wikidata	https://www.wikidata.org/wiki/Q1446839
concepts[9].display_name	Routing (electronic design automation)
concepts[10].id	https://openalex.org/C17020691
concepts[10].level	5
concepts[10].score	0.40021511912345886
concepts[10].wikidata	https://www.wikidata.org/wiki/Q139677
concepts[10].display_name	Operator (biology)
concepts[11].id	https://openalex.org/C38349280
concepts[11].level	2
concepts[11].score	0.39187943935394287
concepts[11].wikidata	https://www.wikidata.org/wiki/Q1434290
concepts[11].display_name	Flow (mathematics)
concepts[12].id	https://openalex.org/C170334043
concepts[12].level	3
concepts[12].score	0.36214226484298706
concepts[12].wikidata	https://www.wikidata.org/wiki/Q6934437
concepts[12].display_name	Multi-commodity flow problem
concepts[13].id	https://openalex.org/C2779313249
concepts[13].level	2
concepts[13].score	0.33432912826538086
concepts[13].wikidata	https://www.wikidata.org/wiki/Q7371615
concepts[13].display_name	Flow routing
concepts[14].id	https://openalex.org/C11413529
concepts[14].level	1
concepts[14].score	0.3300298750400543
concepts[14].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[14].display_name	Algorithm
concepts[15].id	https://openalex.org/C6802819
concepts[15].level	2
concepts[15].score	0.32767942547798157
concepts[15].wikidata	https://www.wikidata.org/wiki/Q1072174
concepts[15].display_name	Linear system
concepts[16].id	https://openalex.org/C120314980
concepts[16].level	1
concepts[16].score	0.3099290430545807
concepts[16].wikidata	https://www.wikidata.org/wiki/Q180634
concepts[16].display_name	Distributed computing
concepts[17].id	https://openalex.org/C19768560
concepts[17].level	2
concepts[17].score	0.2910956144332886
concepts[17].wikidata	https://www.wikidata.org/wiki/Q320727
concepts[17].display_name	Dependency (UML)
concepts[18].id	https://openalex.org/C2781018962
concepts[18].level	2
concepts[18].score	0.2853243052959442
concepts[18].wikidata	https://www.wikidata.org/wiki/Q5164884
concepts[18].display_name	Container (type theory)
concepts[19].id	https://openalex.org/C124681953
concepts[19].level	2
concepts[19].score	0.2829586863517761
concepts[19].wikidata	https://www.wikidata.org/wiki/Q339062
concepts[19].display_name	Decomposition
concepts[20].id	https://openalex.org/C33923547
concepts[20].level	0
concepts[20].score	0.27004143595695496
concepts[20].wikidata	https://www.wikidata.org/wiki/Q395
concepts[20].display_name	Mathematics
concepts[21].id	https://openalex.org/C130120984
concepts[21].level	2
concepts[21].score	0.2691987454891205
concepts[21].wikidata	https://www.wikidata.org/wiki/Q2835898
concepts[21].display_name	Distributed algorithm
concepts[22].id	https://openalex.org/C48044578
concepts[22].level	2
concepts[22].score	0.25328806042671204
concepts[22].wikidata	https://www.wikidata.org/wiki/Q727490
concepts[22].display_name	Scalability
keywords[0].id	https://openalex.org/keywords/flow-network
keywords[0].score	0.5370845198631287
keywords[0].display_name	Flow network
keywords[1].id	https://openalex.org/keywords/transshipment
keywords[1].score	0.5341137051582336
keywords[1].display_name	Transshipment (information security)
keywords[2].id	https://openalex.org/keywords/maximum-flow-problem
keywords[2].score	0.48314398527145386
keywords[2].display_name	Maximum flow problem
keywords[3].id	https://openalex.org/keywords/minimum-cost-flow-problem
keywords[3].score	0.4695435166358948
keywords[3].display_name	Minimum-cost flow problem
keywords[4].id	https://openalex.org/keywords/acceleration
keywords[4].score	0.4380490183830261
keywords[4].display_name	Acceleration
keywords[5].id	https://openalex.org/keywords/linear-programming
keywords[5].score	0.42991167306900024
keywords[5].display_name	Linear programming
keywords[6].id	https://openalex.org/keywords/construct
keywords[6].score	0.42564690113067627
keywords[6].display_name	Construct (python library)
keywords[7].id	https://openalex.org/keywords/routing
keywords[7].score	0.42303380370140076
keywords[7].display_name	Routing (electronic design automation)
language
locations[0].id	doi:10.48550/arxiv.2511.06581
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url
locations[0].version
locations[0].raw_type	article
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published
locations[0].raw_source_name
locations[0].landing_page_url	https://doi.org/10.48550/arxiv.2511.06581
indexed_in	datacite
authorships[0].author.id	https://openalex.org/A2137046868
authorships[0].author.orcid
authorships[0].author.display_name	Grunau, Christoph
authorships[0].author_position	first
authorships[0].raw_author_name	Grunau, Christoph
authorships[0].is_corresponding	True
authorships[1].author.id	https://openalex.org/A4221944067
authorships[1].author.orcid
authorships[1].author.display_name	Kyng, Rasmus
authorships[1].author_position	middle
authorships[1].raw_author_name	Kyng, Rasmus
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A4223937906
authorships[2].author.orcid
authorships[2].author.display_name	Zuzic, Goran
authorships[2].author_position	last
authorships[2].raw_author_name	Zuzic, Goran
authorships[2].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://doi.org/10.48550/arxiv.2511.06581
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-11-12T00:00:00
display_name	Acceleration for Distributed Transshipment and Parallel Maximum Flow
has_fulltext	False
is_retracted	False
updated_date	2025-11-23T05:10:03.516525
primary_topic
cited_by_count	0
locations_count	1
best_oa_location.id	doi:10.48550/arxiv.2511.06581
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url
best_oa_location.version
best_oa_location.raw_type	article
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	https://doi.org/10.48550/arxiv.2511.06581
primary_location.id	doi:10.48550/arxiv.2511.06581
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url
primary_location.version
primary_location.raw_type	article
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	https://doi.org/10.48550/arxiv.2511.06581
publication_date	2025-11-09
publication_year	2025
referenced_works_count	0
abstract_inverted_index.+	151
abstract_inverted_index.A	52
abstract_inverted_index.a	12, 57, 73, 86, 105, 137, 144, 169
abstract_inverted_index.We	0, 21
abstract_inverted_index.an	36
abstract_inverted_index.as	42
abstract_inverted_index.be	118
abstract_inverted_index.by	24, 46
abstract_inverted_index.et	48, 113
abstract_inverted_index.in	33
abstract_inverted_index.is	56
abstract_inverted_index.of	68, 157
abstract_inverted_index.on	154, 164
abstract_inverted_index.to	5, 63, 72, 111, 167
abstract_inverted_index.us	62
abstract_inverted_index.we	102, 134
abstract_inverted_index.$D$	160
abstract_inverted_index.For	99, 132
abstract_inverted_index.al.	49, 114
abstract_inverted_index.and	8, 18, 26, 124, 139, 161
abstract_inverted_index.are	97
abstract_inverted_index.can	117
abstract_inverted_index.due	110
abstract_inverted_index.for	81
abstract_inverted_index.hop	158
abstract_inverted_index.one	91
abstract_inverted_index.the	43, 66, 69, 129
abstract_inverted_index.via	128
abstract_inverted_index.This	142
abstract_inverted_index.also	135
abstract_inverted_index.both	82
abstract_inverted_index.cost	31, 54, 67, 89, 108
abstract_inverted_index.flow	10
abstract_inverted_index.game	45
abstract_inverted_index.that	60, 104, 148
abstract_inverted_index.this	23
abstract_inverted_index.with	11, 15, 35, 120
abstract_inverted_index.(SODA	115
abstract_inverted_index.2024)	116
abstract_inverted_index.depth	17
abstract_inverted_index.flow,	101
abstract_inverted_index.game.	131
abstract_inverted_index.given	74
abstract_inverted_index.known	41
abstract_inverted_index.solve	6
abstract_inverted_index.where	92
abstract_inverted_index.work.	20
abstract_inverted_index.(ICALP	50
abstract_inverted_index.2022).	51
abstract_inverted_index.allows	61
abstract_inverted_index.linear	30, 53, 58, 107
abstract_inverted_index.recent	3, 106
abstract_inverted_index.rounds	153, 163
abstract_inverted_index.yields	143
abstract_inverted_index.Agarwal	112
abstract_inverted_index.CONGEST	146
abstract_inverted_index.achieve	22, 125
abstract_inverted_index.between	94
abstract_inverted_index.combine	1
abstract_inverted_index.compute	168
abstract_inverted_index.general	155
abstract_inverted_index.maximum	100
abstract_inverted_index.observe	103
abstract_inverted_index.optimal	70
abstract_inverted_index.routing	75
abstract_inverted_index.several	2
abstract_inverted_index.diameter	159
abstract_inverted_index.estimate	65
abstract_inverted_index.networks	156, 166
abstract_inverted_index.operator	59
abstract_inverted_index.parallel	13, 29, 122
abstract_inverted_index.problem.	76
abstract_inverted_index.problems	83
abstract_inverted_index.requires	84, 149
abstract_inverted_index.solution	71
abstract_inverted_index.stronger	87
abstract_inverted_index.suitable	28
abstract_inverted_index.Obtaining	77
abstract_inverted_index.algorithm	14, 147
abstract_inverted_index.augmented	119
abstract_inverted_index.construct	136
abstract_inverted_index.deploying	27
abstract_inverted_index.different	95
abstract_inverted_index.framework	40
abstract_inverted_index.additional	121
abstract_inverted_index.continuous	38
abstract_inverted_index.dependency	127
abstract_inverted_index.developing	25, 85
abstract_inverted_index.minor-free	165
abstract_inverted_index.operations	123
abstract_inverted_index.Jambulapati	47
abstract_inverted_index.\sqrt{n}))$	152
abstract_inverted_index.accelerated	37, 78
abstract_inverted_index.box-simplex	44, 130
abstract_inverted_index.commodities	96
abstract_inverted_index.conjunction	34
abstract_inverted_index.disallowed.	98
abstract_inverted_index.distributed	140
abstract_inverted_index.efficiently	64
abstract_inverted_index.advancements	4
abstract_inverted_index.approximator	55, 109
abstract_inverted_index.dependencies	80
abstract_inverted_index.optimization	39
abstract_inverted_index.$\varepsilon$	79
abstract_inverted_index.approximator,	90
abstract_inverted_index.approximator.	141
abstract_inverted_index.approximators	32
abstract_inverted_index.cancellations	93
abstract_inverted_index.deterministic	138, 145
abstract_inverted_index.multicommodity	88
abstract_inverted_index.transshipment,	133
abstract_inverted_index.$\varepsilon^{-1}$	126
abstract_inverted_index.$(1+\varepsilon)$-maximum	9
abstract_inverted_index.$\tilde{O}(1/\varepsilon)$	16
abstract_inverted_index.$\tilde{O}(m/\varepsilon)$	19
abstract_inverted_index.$\tilde{O}(\varepsilon^{-1}(D	150
abstract_inverted_index.$\tilde{O}(\varepsilon^{-1}D)$	162
abstract_inverted_index.$(1+\varepsilon)$-transshipment	7
abstract_inverted_index.$(1+\varepsilon)$-approximation.	170
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
citation_normalized_percentile