Open Research Index

Minimum cost network flow with interval capacities: The worst-case scenario

Miroslav Rada, Milan Hladík, Elif Radová Garajová, Francesco Carrabs, Raffaele Cerulli, Ciriaco D'Ambrosio

arXivarxiv/2602.01360Feb 1, 2026math.OCscore 0

We study the problem of determining the worst optimal value and characterizing the corresponding worst-case scenarios in minimum cost network flow problems with interval uncertainty in arc capacities. In this setting, each capacity can take any value within its specified lower and upper bounds. We prove that computing the worst optimal value is a strongly NP-hard problem and remains NP-hard even when restricted to series-parallel graphs. Further, we propose a mixed-integer linear programming formulation that computes the exact worst optimal value, as well as a pseudopolynomial-time algorithm…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2602.01360
curl -X POST /api/v1/records/arxiv/2602.01360/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.01360/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'