Primal-dual approximation algorithms for integral flow and multicut in trees

DOI10.1007/BF02523685zbMath0873.68075MaRDI QIDQ679443

Vijay V. Vazirani, Mihalis Yannakakis, Naveen Garg

Publication date: 28 May 1997

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

MAX SNP-hardintegral multicommodity flowminimum multicut problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (only showing first 100 items - show all)

Parameterized graph separation problems ⋮ Routing Concurrent Video Signals over SDH Networks ⋮ Call control with \(k\) rejections ⋮ Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation ⋮ Parameterized Maximum Path Coloring ⋮ Hierarchical \(b\)-matching ⋮ A tight relation between series-parallel graphs and bipartite distance hereditary graphs ⋮ A note on multiflows and treewidth ⋮ A logical approach to multicut problems ⋮ Primal-dual approximation algorithms for feedback problems in planar graphs ⋮ Parameterized complexity and approximation issues for the colorful components problems ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ The maximum integer multiterminal flow problem in directed graphs ⋮ A derandomized approximation algorithm for the critical node detection problem ⋮ A randomized algorithm with local search for containment of pandemic disease spread ⋮ Finding disjoint paths with related path costs ⋮ Partial multicuts in trees ⋮ Exact algorithms and applications for tree-like Weighted Set Cover ⋮ The power of cut-based parameters for computing edge-disjoint paths ⋮ Multicuts in planar and bounded-genus graphs with bounded number of terminals ⋮ All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs ⋮ Designing WDM optical networks using branch-and-price ⋮ The bi-objective critical node detection problem ⋮ Parameterized maximum path coloring ⋮ The connected critical node problem ⋮ Improved parameterized and exact algorithms for cut problems on trees ⋮ The all-or-nothing flow problem in directed graphs with symmetric demand pairs ⋮ Improved algorithms for scheduling unsplittable flows on paths ⋮ Query-competitive algorithms for cheapest set problems under uncertainty ⋮ Approximation algorithms for \(k\)-hurdle problems ⋮ A Preemptive Algorithm for Maximizing Disjoint Paths on Trees ⋮ Approximation and hardness results for label cut and related problems ⋮ An approximation algorithm for the generalized \(k\)-multicut problem ⋮ A unified approach to approximating partial covering problems ⋮ Approximability of sparse integer programs ⋮ Multicut Is FPT ⋮ An approximation algorithm for the \(k\)-prize-collecting multicut on a tree problem ⋮ On the generalized multiway cut in trees problem ⋮ Multicut in trees viewed through the eyes of vertex cover ⋮ Restricted vertex multicut on permutation graphs ⋮ On complexity, representation and approximation of integral multicommodity flows ⋮ Tree metrics and edge-disjoint \(S\)-paths ⋮ Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs ⋮ Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs ⋮ Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity ⋮ On the advantage of overlapping clusters for minimizing conductance ⋮ Cut problems in graphs with a budget constraint ⋮ Evader interdiction: algorithms, complexity and collateral damage ⋮ Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs ⋮ Walrasian equilibrium: Hardness, approximations and tractable instances ⋮ On the complexity of the multicut problem in bounded tree-width graphs and digraphs ⋮ Constant-time local computation algorithms ⋮ Finding edge-disjoint paths in networks: an ant colony optimization algorithm ⋮ How to Cut a Graph into Many Pieces ⋮ The critical node detection problem in networks: a survey ⋮ Covering problems in edge- and node-weighted graphs ⋮ An FPT algorithm for planar multicuts with sources and sinks on the outer face ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Disjoint paths in sparse graphs ⋮ A preemptive algorithm for maximizing disjoint paths on trees ⋮ Complexity of the critical node problem over trees ⋮ Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree ⋮ Path problems in generalized stars, complete graphs, and brick wall graphs ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Solution methods for the vertex variant of the network system vulnerability analysis problem ⋮ The checkpoint problem ⋮ Max-multiflow/min-multicut for G+H series-parallel ⋮ On the hardness of finding near-optimal multicuts in directed acyclic graphs ⋮ Correlation clustering in general weighted graphs ⋮ Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees ⋮ Wavelength assignment in multifiber star networks ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ On structural parameterizations of the edge disjoint paths problem ⋮ Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor ⋮ Multicommodity flows in tree-like networks ⋮ Maximum edge-disjoint paths in planar graphs with congestion 2 ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ Line planning, path constrained network flow and inapproximability ⋮ Cardinality constrained and multicriteria (multi)cut problems ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ Path hitting in acyclic graphs ⋮ On three approaches to length-bounded maximum multicommodity flow with unit edge-lengths ⋮ Improved algorithms for the multicut and multiflow problems in rooted trees ⋮ A simple algorithm for multicuts in planar graphs with outer terminals ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths ⋮ A simple rounding scheme for multistage optimization ⋮ Multicuts and integral multiflows in rings ⋮ Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties ⋮ Vertex covering by paths on trees with its applications in machine translation ⋮ A fixed-parameter tractability result for multicommodity demand flow in trees ⋮ Clustering with qualitative information ⋮ New results on planar and directed multicuts ⋮ Integer plane multiflow maximisation: one-quarter-approximation and gaps ⋮ Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations ⋮ Multiway cut and integer flow problems in trees ⋮ Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem ⋮ Primal-dual approximation algorithms for a packing-covering pair of problems ⋮ A greedy algorithm for multicut and integral multiflow in rooted trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Tight integral duality gap in the Chinese postman problem
• Über die Maximalzahl kantendisjunkter A-Wege
• Graph minors. XIII: The disjoint paths problem
• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• An Almost Linear-Time Algorithm for Graph Realization
• A linear-time approximation algorithm for the weighted vertex cover problem
• On the multiway cut polyhedron
• On some connectivity properties of Eulerian graphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• The Complexity of Multiterminal Cuts
• On the hardness of approximating minimization problems
• A General Approximation Technique for Constrained Forest Problems
• Efficient probabilistically checkable proofs and applications to approximations
• Approximate max-flow min-(multi)cut theorems and their applications
• A primal-dual approximation algorithm for generalized Steiner network problems

This page was built for publication: Primal-dual approximation algorithms for integral flow and multicut in trees