The maximum congested cut problem and its robust counterpart: Exact and approximation algorithms for the single and the multicommodity case

DOI10.1002/NET.20205zbMATH Open1181.90276OpenAlexW4246409578MaRDI QIDQ5449665FDOQ5449665

Authors: Maria Grazia Scutellà 

Publication date: 12 March 2008

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20205

Recommendations

• Fast approximation algorithms for multicommodity flow problems
• Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Improved approximations for the minimum-cut ratio and the flux

zbMATH Keywords

sparsest cutlinear fractional combinatorial optimizationcut congestion

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Parametric flows, weighted means of cuts, and fractional combinatorial optimization
• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
• Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut

Cited In (2)

• A mixed integer model for the sparsest cut problem
• Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem

This page was built for publication: The maximum congested cut problem and its robust counterpart: Exact and approximation algorithms for the single and the multicommodity case

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