CS Paper Radar

Network Design against the Bullwhip Effect in Complex Supply Chains

Lauren Bogo, Dominic Liao-McPherson

eess.SY ·submitted 2026-09-23 22:04 UTC · v1
unusual

Abstract

This paper studies the bullwhip effect, the amplification of demand fluctuations into larger order fluctuations upstream, in supply chain networks where each firm orders from several suppliers over routes with different lead times. We show that on a directed acyclic network every response from demand to orders is a sum over paths of products of nodal responses, so that the stability and stability margins of the network are determined by those of its individual nodes, and that a node which splits its orders across routes of different lengths gains margin it can spend on a higher gain and a faster response. We then minimize the worst-case amplification of the network by choosing how each firm splits its orders among its suppliers, which route lead times to shorten, and each firm's ordering gain, with gradients from one adjoint pass per demand node and frequency. On a 14-city network the optimized design amplifies 20~dB less than cost-minimal routing and 17~dB less than a design that shortens the longest routes with the same budget, and is better connected than either. Amplification is therefore a property of routing and delay, not only of the ordering policy, and designing against it also makes the network more robust to a lost route.

Comment
11 pages, 10 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS ·2026-11-04 ·Iman Gholami, MohammadTaghi Hajiaghayi
theory similarity 0.53
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

Optimizing Multi-Tier Intermediation in Programmatic Advertising: A DAG-Based Mechanism for Supply Path Optimization

cs.AI ·2026-11-08 ·Amelia Bădică, Costin Bădică
benchmark similarity 0.53
Abstract

Digital programmatic advertising operates through complex, multi-hop supply chains. The opacity of these intermediary networks leads to significant efficiency losses, often referred to as the ``ad-tech tax.'' While current industry practices utilize heuristic Supply Path Optimization (SPO) to trim inefficient routes, they fail to optimize the equilibrium of the entire network. This paper extends previous work on Directed Acyclic Graph (DAG) intermediation models by applying them to traceable programmatic supply chains mapped via the OpenRTB SupplyChain object. We introduce multi-attribute utility functions and Mixed-Integer Linear Programming (MILP) to account for substitutable routing (OR nodes) and percentage-based fee structures. Furthermore, we outline a computational methodology and experimental framework using public \texttt{schain} and \texttt{sellers.json} data to benchmark optimal Nash social welfare against current uncoordinated market outcomes.

0.33

Stochastic Network Speed Scaling with Competitive Ratios Independent of the Network

cs.DS cs.PF ·2026-10-02 ·Yash Khanna
theory similarity 0.51
Abstract · 14 pages, 2 figures, 1 table

In network speed scaling, jobs arrive over time at a network of servers whose speeds can be tuned, every job must be processed by the servers along one of its allowed routes, and the goal is to minimize the total flow time plus the total energy. For stochastic arrivals, the competitive ratio of Vaze and Nair depends on the network, through the lengths of the routes it uses. We show that this dependence can be removed: we give an algorithm, which routes the jobs by solving a convex program and runs every server at a fixed speed, whose competitive ratio depends only on the power functions; for $P(s)=s^2$, it is at most the golden ratio $\varphi\approx1.618$. The key idea is a lower bound on the optimal cost which, like the cost of our algorithm, is a sum over the servers of a function of each server's load, so the analysis reduces to a single server. We also show that the routing rule of Vaze and Nair can be a factor $Ω(L)$ away from optimal, where $L$ is the length of the longest route.

0.31

Network Origins of the Money-Output Relation

cs.SI econ.TH ·2026-09-29 ·Vipin P Veetil
similarity 0.51
Abstract

This paper develops a dynamic production-network model in which monetary non-neutrality emerges under fully flexible prices. Firms finance intermediate-input purchases from current nominal balances, and intermediate goods arrive with heterogeneous lead times across suppliers. A monetary shock then has two distinct effects. The first is miscoordination: because production uses dated input bundles assembled under past nominal conditions, the shock disturbs the composition of usable inputs (within and across firms) and thereby generates a deadweight loss. The second is reallocation: because the incidence of the shock is tilted toward smaller firms, which are disproportionately downstream, the shock redistributes resources along the supply chain. More specifically, positive shocks push resources downstream, negative shocks pull them upstream. This means that under a negative shock, both the miscoordination and the reallocation effect reduce downstream output and therefore GDP. Under a positive shock, reallocation raises GDP while miscoordination reduces it. The money-output relation is therefore sign-asymmetric: negative shocks generate sharp contractions, while positive shocks generate at most mild expansions, and sometimes none. Computational experiments on a reconstructed US production network generate output declines after a monetary contraction that are about three times as large as the increases after a monetary expansion.

0.28

Targeting Interventions for Volatility Reduction in Network Systems - Part I: Idiosyncratic Shocks

cs.GT ·2026-10-23 ·Luca Damonte, Leonardo Cianfanelli, Giacomo Como, Fabio Fagnani
similarity 0.51
Abstract · 13 pages, 7 figures

We study optimal intervention design problems aimed at minimizing the aggregate volatility in network systems. We consider linear network equilibrium models arising in network games, production networks, and opinion dynamics, where exogenous shocks hitting a few nodes can propagate through the network and cause detrimental systemic effects. Focusing on idiosyncratic shocks, we first identify a general network centrality measure that determines the amplification factor of the variance of each node's shock to the aggregate system volatility, and show that, in relevant special cases, it reduces to Katz-Bonacich, cycle, and concentration centralities. We then consider a system planner who can attenuate the shocks on the nodes, subject to a budget constraint, so as to minimize the aggregate volatility. We solve this problem analytically and show that its solution has a water-filling-type structure: for low budget, the intervention is concentrated on the node(s) maximizing a quantity ω_i that combines the shock's variance, the node's centrality, and the intervention cost; as the budget increases, more and more nodes are targeted, and for sufficiently large budget every node with ω_i > 0 receives an intervention proportional to ω_i. Finally, we study a robust version of the problem, where the planner minimizes the volatility against the worst-case vector of shock variances chosen by an adversary within a given budget. We solve this min-max problem analytically and show that its solution also has a water-filling-type structure, with the ratio between the node's centrality and the square root of the adversarial cost playing the role of ω_i.

0.32

Buy-at-Bulk Facility Location on Trees

cs.DS ·2026-08-26 ·Shamisa Nematollahi, Daniel Vaz
similarity 0.50
Abstract · Presented at WAOA 2025

We consider the buy-at-bulk facility location problem (BBFL), a problem combining the classic facility location problem with buy-at-bulk network design, which finds motivation in telecommunication networks. In it, we are given a graph with edge lengths, opening costs and demands for each vertex, and a monotone and subadditive capacity-cost function, and our task is to open facilities on a subset of the vertices and route the demand from each vertex to these facilities. The cost of a solution (which we want to minimize) is given by the opening costs of the chosen facilities, plus the cost on each edge, which is given by its length times the cost of providing enough capacity for the demands through the edge, given by the capacity-cost function. A common variant of the problem, the $k$-cable facility location problem (kCFL), considers the case where capacity is provided by buying copies of given cable types, each with a certain capacity and cost. We study BBFL on tree instances and show, for the unit-demand and splittable variants, that the problem admits a PTAS (a $(1+ε)$-approximation for any $ε> 0$). We also consider kCFL in the new setting of cable-unsplittable demands, where the demand of a vertex cannot be split among multiple cables. We show that the problem is NP-hard to approximate to a factor better than $3/2$ on stars, and then provide an algorithm for tree instances that outputs a solution with optimal cost, but which exceeds the capacity on each cable by a factor of $1+ε$. As a consequence, we show that the problem has a $2$-approximation algorithm on trees.

0.28

Online Network Design with Maximum Delay and Stochastic Arrivals

cs.DS ·2026-11-10 ·Tianhang Lu
theory similarity 0.49
Abstract

We study online network services that combine pending requests into batches. Each batch pays for its spatial service and for the waiting time of its oldest request. The objective is the sum of these costs over all batches. Thus requests can share both a spatial purchase and one maximum-delay charge. We assume independent Poisson arrivals of known rates, while actual requests are revealed only upon arrival. For stateless services, suppose that each type has an attainable minimum cost when served alone, that every batch costs at least the stand-alone minimum of each type it contains, and that one finite-cost action can serve any batch, regardless of its request multiplicities. We give a deterministic algorithm with long-run ratio of expectations $e/(e-1)$ against an unrestricted offline optimum. This factor is optimal, even allowing randomization, already at one request location. The key comparison measures the union of time intervals associated with requests. The theorem applies directly to multi-root and pair aggregation on trees. We also study facility location, where each request pays its own connection distance and the bounded-action assumption can fail. A deterministic policy gives a ratio $3$ for arbitrary nonnegative opening costs. It immediately serves a finite initial set of requests, computes an assignment from their observed arrival gaps, and then keeps that assignment fixed. Its analysis combines Poisson insertion with a time-slice packing bound on the offline optimum. Every guarantee includes the full cost of completing finite inputs without an end-of-input signal.

0.15

Capacity-Aware Redistribution Control for Mitigation of Cascading Failures in Networks

eess.SY math.OC ·2026-11-18 ·Ujjwal Pratap, Christian A. Hans
similarity 0.48
Abstract

This paper studies the control of irreversible cascading failures in networks with finite node capacities. Each node carries a nonnegative divisible quantity, referred to as load, and fails irreversibly when its load exceeds its capacity. The network dynamics are represented by topology-dependent row-stochastic matrices. When nodes fail, these matrices must be updated. However, directly deleting rows and columns corresponding to failed nodes can reduce the total load in the network. We therefore introduce a topology update that preserves unit row sums and quantifies any unserved load explicitly. We derive the resulting load-balance relation and a necessary and sufficient condition for lossless redistribution after simultaneous failures. Based on these results, we formulate a two-stage optimization problem: the first stage minimizes unserved load, and the second stage minimizes the highest capacity utilization among the surviving nodes. Simulations on grid and Barabasi-Albert networks show that, unlike the standard equal and residual-capacity redistribution approaches, the proposed method prevents secondary failures in all tested cases, with a tradeoff against served load on scale-free networks.

0.32