Greedy splitting algorithms for approximating multiway partition problems

DOI10.1007/s10107-004-0510-2zbMath1177.90403OpenAlexW2026838540MaRDI QIDQ1769071

Toshihide Ibaraki, Liang Zhao, Hiroshi Nagamochi

Publication date: 17 March 2005

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

Full work available at URL: https://doi.org/10.1007/s10107-004-0510-2

zbMATH Keywords

Approximation algorithmSubmodular functionHypergraph partitionMultiterminal cutMultiway partition problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

Global and fixed-terminal cuts in digraphs, Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems, Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem, Hypergraph \(k\)-cut in randomized polynomial time, Algorithmic aspects of homophyly of networks, Submodular Cost Allocation Problem and Applications, On the Huffman and alphabetic tree problem with general cost functions, Mathematical methods for physical layout of printed circuit boards: an overview, Exploiting structure of chance constrained programs via submodularity, Fixed parameter approximation scheme for min-max \(k\)-cut, Fixed parameter approximation scheme for min-max \(k\)-cut, Unnamed Item, Approximation algorithms for vertex happiness, Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time, New approximations and hardness results for submodular partitioning problems

Cites Work

• A new and improved algorithm for the 3-cut problem
• A note on formulations for the \(A\)-partition problem on hypergraphs
• Minimizing symmetric submodular functions
• Partitions and network reliability
• An improved approximation algorithm of MULTIWAY CUT.
• Connectivity and edge-disjoint spanning trees
• Rounding algorithms for a geometric embedding of minimum multiway cut
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Optimal attack and reinforcement of a network
• A new approach to the maximum-flow problem
• Multi-Terminal Network Flows
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• The Complexity of Multiterminal Cuts
• Finding k Cuts within Twice the Optimal
• Counterexamples for Directed and Node Capacitated Cut-Trees
• Approximation Algorithms for Min-k-Overlap Problems Using the Principal Lattice of Partitions Approach
• Cutsets and partitions of hypergraphs
• Combinatorial optimization. Theory and algorithms
• Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item