scientific article; zbMATH DE number 7053315

zbMath1421.68204MaRDI QIDQ5743436

Julia Chuzhoy, Yuan Zhou, Yury Makarychev, Aravindan Vijayaraghavan

Publication date: 10 May 2019

Full work available at URL: https://dl.acm.org/citation.cfm?id=2095179

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

A new approximation algorithm for the unbalanced min \(s\)-\(t\) cut problem ⋮ Capacity factors in a point-to-point network ⋮ Unbalanced graph cuts with minimum capacity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Short length Menger's theorem and reliable optical routing
• Flows over edge-disjoint mixed multipaths and applications
• On the hardness of approximating Multicut and Sparsest-Cut
• On multiroute maximum flows in networks
• Public-key cryptography from different assumptions
• Detecting high log-densities
• Graph expansion and the unique games conjecture
• Unbalanced Graph Partitioning
• Proof verification and the hardness of approximation problems
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Algorithms for 2-Route Cut Problems
• Relations between average case complexity and approximation complexity
• Euclidean distortion and the sparsest cut
• Probabilistic checking of proofs
• The Complexity of Multiterminal Cuts
• A Parallel Repetition Theorem
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions
• Algorithms for Fault‐Tolerant Routing in Circuit‐Switched Networks
• Algorithms – ESA 2005
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁
• Expander flows, geometric embeddings and graph partitioning
• Vertex Sparsifiers: New Results from Old Techniques