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

DOI10.1002/NET.20205MaRDI QIDQ5449665zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

cut congestionlinear fractional combinatorial optimizationsparsest cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

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

Cites work

• \(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
• Parametric flows, weighted means of cuts, and fractional combinatorial optimization

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)