On the minimum s-t cut problem with budget constraints

DOI10.1007/S10107-023-01987-9MaRDI QIDQ6120941zbMATH OpenFDO

Authors Hassene Aissi, A. R. Mahjoub

Publication date 21 February 2024

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10107-023-01987-9

zbMATH Keywords

budget constraintslinear programmingminimum \(s-t\) cut problem

Mathematics Subject Classification ID

Linear programming (90C05) Integer programming (90C10) Combinatorial optimization (90C27)

Recommendations

• On the linear relaxation of the \(s-t\)-cut problem with budget constraints
• Cut problems in graphs with a budget constraint
• Cut Problems in Graphs with a Budget Constraint
• On the complexity and approximability of budget-constrained minimum cost flows
• Budget-constrained minimum cost flows

Cites work

• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• A new approximation algorithm for the unbalanced min s-t cut problem
• A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts
• Algorithms – ESA 2005
• Hardness and approximation for network flow interdiction
• How easy is local search?
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Multicriteria global minimum cuts
• Multicriteria Optimization
• New approaches to multi-objective optimization
• On a multicriteria shortest path problem
• On the structure of all minimum cuts in a network and applications
• Properties of vertex packing and independence system polyhedra
• Simple Local Search Problems that are Hard to Solve
• Suboptimal cuts: their enumeration, weight and number (extended abstract)
• The constrained minimum spanning tree problem
• The constrained minimum weighted sum of job completion times problem

This page was built for publication: On the minimum \(s-t\) cut problem with budget constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6120941)