Approximating submodular \(k\)-partition via principal partition sequence

DOI10.1137/24m1638604MaRDI QIDQ6654129

Weihang Wang, Karthekeyan Chandrasekaran

Publication date: 18 December 2024

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

partitionapproximation algorithmssubmodular functionsprincipal lattice of partitions

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Minimum cost subpartitions in graphs
• A faster algorithm for computing the principal sequence of partitions of a graph
• The principal lattice of partitions of a submodular function
• The realization of finite state machines by decomposition and the principal lattice of partitions of a submodular function.
• Improving graph partitions using submodular functions.
• Greedy splitting algorithms for approximating multiway partition problems
• On the \(k\)-cut problem
• New approximations and hardness results for submodular partitioning problems
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
• Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
• Testing Coverage Functions
• LP Relaxation and Tree Packing for Minimum $k$-Cut
• Optimal attack and reinforcement of a network
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Finding k Cuts within Twice the Optimal
• Approximation Algorithms for Min-k-Overlap Problems Using the Principal Lattice of Partitions Approach
• Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
• Fast and Deterministic Approximations for k-Cut.

This page was built for publication: Approximating submodular \(k\)-partition via principal partition sequence