Maximizing the minimum source-sink path subject to a budget constraint
From MaRDI portal
Publication:4143044
DOI10.1007/BF01584329zbMath0366.90115OpenAlexW2094463866MaRDI QIDQ4143044
Gary C. Harding, D. R. Fulkerson
Publication date: 1977
Published in: Mathematical Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01584329
Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Deterministic network models in operations research (90B10)
Related Items
Efficient algorithms for robustness in resource allocation and scheduling problems ⋮ Optimizing dynamic investment decisions for railway systems protection ⋮ Minimizing a stochastic maximum-reliability path ⋮ Reformulation and sampling to solve a stochastic network interdiction problem ⋮ Shortest path network interdiction with asymmetric information ⋮ A class of algorithms for mixed-integer bilevel min-max optimization ⋮ A bilevel partial interdiction problem with capacitated facilities and demand outsourcing ⋮ Optimal approaches for upgrading selective obnoxious \(p\)-median location problems on tree networks ⋮ Upgrading the 1-center problem with edge length variables on a tree ⋮ Solving multi-period interdiction via generalized Bender's decomposition ⋮ Modeling Defender-Attacker Problems as Robust Linear Programs with Mixed-Integer Uncertainty Sets ⋮ Matching interdiction ⋮ Upgrading min-max spanning tree problem under various cost functions ⋮ A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths ⋮ Interdicting the activities of a linear program -- a parametric analysis ⋮ Upgrading edges in the graphical TSP ⋮ The \(p\)-median problem with upgrading of transportation costs and minimum travel time allocation ⋮ Logic-based Benders decomposition for wildfire suppression ⋮ Shortest path interdiction problem with convex piecewise-linear costs ⋮ Upgrading \(p\)-median problem on a path ⋮ A survey on mixed-integer programming techniques in bilevel optimization ⋮ Approximation algorithms for \(k\)-hurdle problems ⋮ A two‐stage network interdiction‐monitoring game ⋮ Distributionally risk‐receptive and risk‐averse network interdiction problems with general ambiguity set ⋮ Attack and interception in networks ⋮ The stochastic interdiction median problem with disruption intensity levels ⋮ Weight reduction problems with certain bottleneck objectives. ⋮ On Nash-solvability in pure stationary strategies of the deterministic \(n\)-person games with perfect information and mean or total effective cost ⋮ Mitigating Interdiction Risk with Fortification ⋮ On short paths interdiction problems: Total and node-wise limited interdiction ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ A note on linearized reformulations for a class of bilevel linear integer problems ⋮ A Brief Overview of Interdiction and Robust Optimization ⋮ Survivable network design under optimal and heuristic interdiction scenarios ⋮ A bilevel mixed-integer program for critical infrastructure protection planning ⋮ Reverse 2-median problem on trees ⋮ Cyclic games and linear programming ⋮ Modeling \(s-t\) path availability to support disaster vulnerability assessment of network infrastructure ⋮ Network interdiction with asymmetric cost uncertainty ⋮ A bi-level model and memetic algorithm for arc interdiction location-routing problem ⋮ New solution approaches for the maximum-reliability stochastic network interdiction problem ⋮ Analysis of budget for interdiction on multicommodity network flows ⋮ Convex hull representation of the deterministic bipartite network interdiction problem ⋮ A nested family of \(k\)-total effective rewards for positional games ⋮ An interdiction game on a queueing network with multiple intruders ⋮ A dynamic reformulation heuristic for generalized interdiction problems ⋮ An exact solution approach for the interdiction median problem with fortification ⋮ Network interdiction to minimize the maximum probability of evasion with synergy between applied resources ⋮ Bottleneck Capacity Expansion Problems with General Budget Constraints ⋮ A class of bottleneck expansion problems ⋮ Heuristics for multi-stage interdiction of stochastic networks ⋮ A game-theoretic approach for downgrading the 1-median in the plane with Manhattan metric ⋮ The multi-terminal maximum-flow network-interdiction problem ⋮ Equilibrium strategies for multiple interdictors on a common network ⋮ Sequential Shortest Path Interdiction with Incomplete Information ⋮ Approximation Algorithms for k-Hurdle Problems ⋮ A survey of network interdiction models and algorithms ⋮ A decomposition approach for stochastic shortest-path network interdiction with goal threshold ⋮ Up- and downgrading the 1-center in a network ⋮ Finding the most vital arcs in a network ⋮ The Shortest Path Interdiction Problem with Randomized Interdiction Strategies: Complexity and Algorithms ⋮ The continuous maximum capacity path interdiction problem ⋮ Identifying the critical road combination in urban roads network under multiple disruption scenarios ⋮ Determining the most vital arcs on the shortest path for fire trucks in terrorist actions that will cause fire ⋮ Sequential Shortest Path Interdiction with Incomplete Information and Limited Feedback
Cites Work
