CS Paper Radar

Optimizing the Steady-State Travel Time of Nash Flows over Time with Capacity Increases

Niklas Dahlmeier, Paul Paschmanns, Laura Ritter, Ruben Skorupinski

cs.DS ·submitted 2026-11-09 14:34 UTC · v1

Abstract

We study budgeted capacity augmentation for single-source single-sink \NFOTs under constant inflow $u_0$. The goal is to increase capacities on arcs subject to a global budget constraint in order to minimize the steady-state travel time in the network. We show that this problem is weakly NP-hard on series-parallel networks and provide an exact pseudopolynomial algorithm as well as a fully polynomial algorithm that attains the optimum travel time for budget $B$ while spending at most $B + \varepsilon\cdot\max\{B,u_0\}$. On general networks the problem becomes strongly NP-hard. Moreover, unless $\text{P} = \text{NP}$, for every fixed $\varepsilon \in (0,1)$, no polynomial-time algorithm can achieve the optimal steady-state travel time while exceeding the budget by at most a factor of $n^{1-\varepsilon}$. Lastly, we give structural properties about steady-state travel time under varying arc capacities. We identify capacity thresholds determined by subsets of $s$-$t$-cuts and show that the travel time is constant in the interior of the cells resulting from the corresponding hyperplane arrangement.

Closest papers

Nearest neighbours by meaning across the whole index.

Generalized Flows over Time: Complexity, Structure and Algorithm

cs.DS ·2026-11-02 ·Siyuan Chen, Shengminjie Chen, Suixiang Gao, Zheyu Jiang, Dun Ma +1 more
publishedtheory similarity 0.70
Abstract · 43pages,7figures;An earlier version of this paper appeared at COCOON 2026

Generalized flows over time constitute a general network flow model that incorporates both transit times and flow losses or gains. We study their complexity, structure, and approximation. We prove that the generalized maximum flow over time problem remains NP-hard under standard binary encoding, even on lossy two-terminal series-parallel networks. The maximum temporally repeated restriction is APX-hard with general gains and NP-hard on lossy networks. We then consider the minimum source supply needed to satisfy a fixed sink demand within a given horizon, and prove that an optimal solution always exists without intermediate storage. On lossy networks, such a solution can additionally use only simple source--sink paths. These structural properties yield a fully polynomial-time approximation scheme via time condensation, with analogous schemes for generalized maximum flows over time and quickest flows with a source-supply budget.

0.38

On the Delay-Constrained Maximum Concurrent Flow Problem

cs.NI math.OC ·2026-09-04 ·Walid Ben-Ameur, Guillaume Beraud-Sudreau, Hervé Kerivin, Sebastien Martin
theory similarity 0.63
Abstract

Real-time services, such as VoIP and large-scale neural network training, require strict transmission delay guarantees. While routing under hop constraints is tractable, real-world delays increase sharply with equipment load, typically modeled using the M/M/1 queuing function where delay is inversely proportional to available bandwidth. We investigate the resulting Delay-Constrained Maximum Concurrent Flow (DCMCF) problem, which seeks to maximize the minimum throughput across all commodities. The problem's complexity stems from the conditional and non-linear nature of the delay constraints, which are active only along the specific paths used by the flow. We prove that DCMCF is strongly NP-hard, even for single-source/single-destination instances. To address the inherent non-convexity of the problem, we introduce a new convex relaxation expressed through second-order cone constraints, obtained from the convex envelope of a function representing the conditional delay associated with a single arc of a given path. The relaxation is shown to outperform existing formulations based on disjunctive programming. Leveraging this result, we develop a polynomial-time approximation algorithm with a provable performance guarantee and present numerical experiments demonstrating the effectiveness of the proposed approach.

0.31

Algorithms with Smoothed Polynomial-Time Complexity for Deterministic Discounted-sum and Mean-payoff Games

cs.GT cs.DS ·2026-10-09 ·Ali Asadi, Krishnendu Chatterjee, Ruichen Luo
similarity 0.61
Abstract

Turn-based deterministic games on graphs are two-player zero-sum games played on finite directed graphs, where the vertex set is partitioned between the Max and the adversarial Min Player. The respective player chooses outgoing edges from their vertices. We consider these games with the classical discounted-sum and mean-payoff objectives. The goal of the Max Player is to maximize the objective against the adversarial Min Player. These games lie in NP $\cap$ coNP and are among the rare combinatorial problems that belong to this complexity class, yet the existence of a polynomial-time algorithm is a major open question. All known deterministic algorithms require exponential time in the worst case, while the classical strategy iteration (policy iteration) algorithm is remarkably efficient in practice, which motivates the study of the smoothed complexity of these games. Previous results established a smoothed polynomial-time bound only for the restricted class of ergodic games and presented only a high-probability guarantee. Our main result is a new analysis technique for a variant of the strategy iteration algorithm, and we show these algorithms achieve smoothed polynomial complexity for general game graphs with both high-probability and expected runtime guarantees. In particular, our result removes the ergodicity restriction of prior work and strengthens the high-probability guarantee to the stronger expected-runtime guarantee, thereby resolving the open question on the smoothed complexity of these games.

0.50

Strengthening Compact Vehicle Routing Formulations through Arc-Flow Aggregation and Refinement

cs.DM math.OC ·2026-11-15 ·Julian Yarkony, Willem-Jan van Hoeve, Anthony Karahalios, Martin Karyamsetty, Soheyl Khalilpourazari +2 more
similarity 0.61
Abstract · 47 pages. Submitted to Transportation Science

Arc-flow formulations can provide strong relaxations for mixed-integer program formulations of vehicle routing problems, but the associated networks may be prohibitively large. We study the setting in which multiple arc flow relaxations may be applied, and introduce a dual-guided aggregation and refinement framework that constructs substantially smaller arc-flow formulations while recovering the LP bound of the original networks. Dual information is used both to identify states that can be aggregated without weakening the bound and to guide node disaggregation. We show that the resulting procedure converges finitely to the arc-flow bound of the full arc-flow formulation. The framework retains the original decision variables, allowing cutting planes to be added directly in the original variable space. Moreover, it produces an explicit MILP formulation without relying on column generation or pricing to determine the arc-flow relaxation bound. We apply our approach to the vehicle routing problem with time windows for which we define two arc flow relaxations, as well as two families of cutting planes over the original variable space. Computational experiments show that strong bounds can be obtained using substantially aggregated networks. The resulting root bounds are competitive with those obtained by the branch-and-price solver RouteOpt, while retaining a formulation that can be solved directly by a general-purpose MILP solver.

0.30

Tolls for Dynamic Equilibrium Flows

cs.GT ·2026-08-12 ·Lukas Graf, Tobias Harks, Julian Schwarz
similarity 0.61
Abstract

We consider dynamic network flows and study the following question: Which dynamic edge flows can be implemented as tolled dynamic equilibrium flows? We study this question for the heterogeneous-user model, where the flow particles are partitioned into populations characterized by their own source,destination-pairs and a cost function associating with any walk and departure time some costs. As our two main results, we first provide a duality-based characterization of implementability of dynamic edge flows for the multi-source, multi-destination case. Secondly, we derive both, a combinatorial and duality-based characterization of implementability of dynamic edge flows for the multi-source, single-destination case. Both results are derived under a fairly general network loading model. For the proof, we make several technical contributions: We formulate a novel infinite dimensional optimization problem, where the goal is to minimize the aggregated costs of the particles with respect to the fixed network loading induced by the given edge flow. This requires the recently introduced concept of autonomous network loadings for which we show several new structural insights. In particular, we give an alternative (tighter) characterization of the existence of autonomous network loadings for our setting by deriving a generalization of a result of M.A. Zareckiĭ on the Lusin $N^{-1}$ property of absolutely continuous monotone functions which may also be of independent interest. These insights allow us to prove the stated characterizations under the assumption of strong duality. Finally, for the case of a single-destination, we are able to provide a non-trivial proof that this assumption is always fulfilled for finitely supported edge flows with costs representing weighted travel times.

0.04

Nonuniform Buy-at-Bulk Network Design: Improved Approximation and LP Integrality Gap

cs.DS ·2026-11-04 ·Iman Gholami, MohammadTaghi Hajiaghayi
theory similarity 0.61
Abstract

In nonuniform buy-at-bulk network design, we are given an undirected graph and $h$ terminal pairs with positive demands, and we must route every demand at minimum total cost when each network resource has two independent parameters: a fixed buying price paid once if the resource is used, and a per-unit rental cost (or physical length) paid proportionally to the traffic it carries. Unlike the uniform-cost or single-sink variants, the general multicommodity problem allows unrelated buying and rental metrics across arbitrary source--sink pairs, arbitrary demands, and both edge and node resources. We give a deterministic polynomial-time $O(\log^2 h / (\log\log h)^2)$-approximation algorithm for undirected nonuniform buy-at-bulk network design. The guarantee holds for edge costs, node costs, and their combination, and applies to arbitrary positive rational demands with no dependence on the number of vertices or the numerical demand ratio. This improves upon the $O(\log^4 h)$ bound of Chekuri, Hajiaghayi, Kortsarz, and Salavatipour (2010) for unrestricted instances. Our result also establishes the same $O(\log^2 h / (\log\log h)^2)$ upper bound on the integrality gap of the natural affine multicommodity flow LP, bounding integral buying and rental costs separately against their fractional counterparts and preserving zero rental budgets exactly.

0.25

Strongly Polynomial Parallel Maximum Flow Revisited

cs.DS ·2026-08-12 ·Adam Karczmarz, Paweł Pilarski
published similarity 0.60
Abstract · Extended abstract to appear in ESA 2026

We study the maximum flow problem in directed networks with real capacities in the parallel setting. For a network with $n$ vertices and $m$ arcs, we show that a randomized parallel implementation of a variant of the strongly polynomial max-flow algorithm of Dadush, Orlin, Sidford, and Végh [SODA 2026] runs in $\tilde{O}(mn)$ work and $\tilde{O}(m)$ depth. This improves upon the previously described tradeoffs between work and depth for strongly polynomial parallel maximum flow algorithms: earlier $\tilde{O}(n^3)$-work algorithms have $\tilde{O}(n^2)$ depth [Shiloach and Vishkin, J. Algorithms 1982; Goldberg and Tarjan, J. ACM 1988], while the known $\tilde{O}(m)$-depth approach uses $\tilde{O}(mn^3)$ work [Orlin, Oper. Res. 1993].

0.22

A polynomial-time approximation scheme for the weighted Euclidean Minimum Latency Problem in fixed dimension

cs.DS math.CO ·2026-11-11 ·Daniel Skachkov, Yuriy Dorn
similarity 0.60
Abstract

In the Traveling Salesman Problem, a route must visit all customers and return to its starting point while minimizing its total length. The Minimum Latency Problem, also known as the Traveling Repairman Problem, instead minimizes the sum of the times at which customers are first visited. We give a deterministic polynomial-time approximation scheme for the weighted Euclidean Minimum Latency Problem in every fixed dimension, with arbitrary nonnegative customer weights. Our proof restricts the form of a solution in three steps, each with a controlled increase in cost. First, a decomposition based on Sitters' method assigns customers to phases that start and end at the root. Second, within each phase, we divide the route into a constant number of blocks and charge each customer at the end of its assigned block. The resulting objective is a nonnegative linear combination of block lengths. Third, we add an auxiliary dimension and use a fixed Minkowski norm to close each block path into a tour. Arora's closed-tour estimate then gives paths that cross the boundaries of a common dissection only at designated portals and a bounded number of times per face. A dynamic program optimizes the restricted objective, and projecting its paths back to the original space gives the final route. Rounding weights and coordinates keeps the state space polynomial.

0.30