Approximating submodular k-partition via principal partition sequence

DOI10.1137/24M1638604MaRDI QIDQ6654129zbMATH OpenFDO

Authors Karthekeyan Chandrasekaran, Weihang Wang

Publication date 18 December 2024

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

Full work available at URL https://doi.org/10.1137/24M1638604

zbMATH Keywords

approximation algorithmspartitionprincipal lattice of partitionssubmodular functions

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Min-max partitioning of hypergraphs and symmetric submodular functions
• A polynomial time algorithm for finding a minimum 4-partition of a submodular function
• Algorithms and lower bounds for submodular cuts and approximating submodular functions

Cites work

• A faster algorithm for computing the principal sequence of partitions of a graph
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
• Approximation Algorithms for Min-k-Overlap Problems Using the Principal Lattice of Partitions Approach
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Fast and Deterministic Approximations for k-Cut.
• Finding k Cuts within Twice the Optimal
• Greedy splitting algorithms for approximating multiway partition problems
• Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
• Improving graph partitions using submodular functions.
• Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
• LP relaxation and tree packing for minimum k-cut
• Minimum cost subpartitions in graphs
• New approximations and hardness results for submodular partitioning problems
• On the \(k\)-cut problem
• On the hardness of approximating the \(k\)-\textsc{Way Hypergraph Cut} problem
• Optimal attack and reinforcement of a network
• Testing coverage functions
• 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.
• Tree packing and approximating k-cuts

Cited in

(4)

• Min-max partitioning of hypergraphs and symmetric submodular functions
• A polynomial time algorithm for finding a minimum 4-partition of a submodular function
• Approximating submodular matroid-constrained partitioning
• \(\{s,t\}\)-separating principal partition sequence of submodular functions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6654129)